Rafail Ostrovsky - Publications

Simple and Efficient Leader Election In The Full Information Model.

Rafail Ostrovsky, Sridhar Rajagopalan, Umesh Vazirani


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/2 - ε for any positive ε. Our Protocols are extremely simple.

comment: Appeared In Proceedings of Twenty-sixth ACM Symposium on Theory of Computing (STOC-94) Montreal, Quebec, Canada, May 23-25, 1994.

Fetch PostScript file of the paper     Fetch PDF file of the paper

Back to Publications List