Rafail Ostrovsky and Sridhar Rajagopalan and Umesh Vazirani

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-94-800

, 1994

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.

---

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},
    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