Fast leader-election protocols with bounded cheaters' edge

ABSTRACT

We study the leader election problem on n players in the asynchronous full-information model. Our main contention is that the most commonly used performance measure for leader-election protocols, called resilience, is unable to discern whether a small number of players can exercise disproportionate influence on the outcome of a protocol, or not. As a remedy we propose a new quantity, named cheaters' edge, which roughly describes by what multiplicative factor malicious players may increase, through cheating, their probability of getting elected. Arguably, a good protocol must have bounded cheaters' edge.We present polynomial-time constructions of new leader-election protocols that are fast, in terms of the rounds required (5, 5 log n, and log n rounds, respectively), but moreover exhibit bounded cheaters' edge under progressively looser restrictions on the number t of malicious players: t < Θn / log n, t < Θn / √log n log log n, and, eventually, no restriction at all---without relying on any a priori knowledge of t. The latter of these three protocols constitutes the first constructive solution to a problem posed by Alon and Naor more than a decade ago.

REFERENCES

• 1: M. Ajtai and N. Linial. The influence of large coalitions. Combinatorica, 13(2):129--145, 1993.
• 2: Noga Alon , Moni Naor, Coin-flipping games immune against linear-sized coalitions, SIAM Journal on Computing, v.22 n.2, p.403-417, April 1993 [doi>10.1137/0222030]
• 3: M. Ben-Or and N. Linial. Collective coin flipping. In S. Micali, editor, Randomness and Computation, pages 91--115. Academic Press, New York, 1990. Preliminary version in FOCS 26th, pages 408--416.
• 4: Ravi B. Boppana , Babu O. Narayanan, Perfect-Information Leader Election with Optimal Resilience, SIAM Journal on Computing, v.29 n.4, p.1304-1320, Feb. 2000 to March 2000 [doi>10.1137/S0097539796307182]
• 5: Jason Cooper , Nathan Linial, Fast perfection-information leader-election protocol with linear immunity, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.662-671, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167258]
• 6: Uriel Feige, Noncryptographic Selection Protocols, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.142, October 17-18, 1999
• 7: Oded Goldreich , Shafi Goldwasser , Nathan Linial, Fault-tolerant Computation in the Full Information Model, SIAM Journal on Computing, v.27 n.2, p.506-544, April 1998 [doi>10.1137/S0097539793246689]
• 8: Rafail Ostrovsky , Sridhar Rajagopalan , Umesh Vazirani, Simple and efficient leader election in the full information model, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.234-242, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195141]
• 9: Alexander Russell , Michael Saks , David Zuckerman, Lower bounds for leader election and collective coin-flipping in the perfect information model, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.339-347, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301337]
• 10: Alexander Russell , David Zuckerman, Perfect information leader election in log ^* n+0(1) rounds, Journal of Computer and System Sciences, v.63 n.4, p.612-626, December 2001 [doi>10.1006/jcss.2001.1776]
• 11: Michael Saks, A robust noncrytographic protocol for collective coin flipping, SIAM Journal on Discrete Mathematics, v.2 n.2, p.240-244, May 1989 [doi>10.1137/0402020]
• 12: David Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, v.11 n.4, p.345-367, Dec. 1997

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

General Terms:
Algorithms, Theory

Keywords:
coin-flipping, distributed computing, leader election