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