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 $\beta N$ 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 $\frac{1}{2} - \epsilon$ for any positive $\epsilon$.
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 |