Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Simple and Efficient Leader Election in the Full Information Model

Rafail Ostrovsky, Sridhar Rajagopalan and Umesh Vazirani

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-94-800
March 1994

http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/CSD-94-800.pdf

In this paper, we study the leader election problem in the full information model. We show two results in this context. First, we exhibit a constructive O(log N) round protocol that is resilient against linear size coalitions. That is, our protocol is resilient against any coalition of size less then beta N for some constant (but small) value of beta. Second, we provide an easy, non-constructive probabilistic argument that shows the existence of O(log N) round protocol in which beta can be made as large as 1/2 - epsilon for any positive epsilon. Our protocols are extremely simple.


BibTeX citation:

@techreport{Ostrovsky:CSD-94-800,
    Author = {Ostrovsky, Rafail and Rajagopalan, Sridhar and Vazirani, Umesh},
    Title = {Simple and Efficient Leader Election in the Full Information Model},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1994},
    Month = {Mar},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/6314.html},
    Number = {UCB/CSD-94-800},
    Abstract = {In this paper, we study the leader election problem in the full information model. We show two results in this context. First, we exhibit a constructive <i>O</i>(log <i>N</i>) round protocol that is resilient against linear size coalitions. That is, our protocol is resilient against any coalition of size less then beta<i>N</i> for some constant (but small) value of beta. Second, we provide an easy, non-constructive probabilistic argument that shows the existence of <i>O</i>(log <i>N</i>) round protocol in which beta can be made as large as 1/2 - epsilon for any positive epsilon. Our protocols are extremely simple.}
}

EndNote citation:

%0 Report
%A Ostrovsky, Rafail
%A Rajagopalan, Sridhar
%A Vazirani, Umesh
%T Simple and Efficient Leader Election in the Full Information Model
%I EECS Department, University of California, Berkeley
%D 1994
%@ UCB/CSD-94-800
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1994/6314.html
%F Ostrovsky:CSD-94-800