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://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/6314.html
%F Ostrovsky:CSD-94-800