Simple and efficient leader election in the full information model
Rafail Ostrovsky, Sridhar Rajagopalan, Umesh V. Vazirani · 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 N for some constant (but small) value of. Second, we provide an easy, non-constructive probabilistic argument that shows the existence of O(log N) round protocol in which can be made as large as 1, for any positive. Our 2 protocols are extremely simple.