Simple and Efficient Leader Election In The Full Information Model.
Rafail Ostrovsky, Sridhar Rajagopalan, Umesh Vazirani
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 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 |