Scalable leader election

ABSTRACT

In the leader election problem, there are n processors of which (1 - b)n are good. The problem is to design a distributed protocol to elect a good leader from the set of all processors. In this paper, we present a scalable leader election protocol. Our protocol is scalable in the sense that each good processor sends and processes a number of bits which is only polylogarithmic in n. (We assume no limit on the number of messages sent by bad processors.) For b < 1/3, our protocol elects a good leader with constant probability and ensures that a 1 - o(1) fraction of the good processors know this leader.We assume a point-to-point full information model. This is similar to the full information model, but harder in the sense that in a given round, a bad processor may send different messages to different processors, rather than having to broadcast the same message to every processor.To the best of our knowledge, we present the first leader election protocol that ensures that each good processor sends and processes a sublinear number of bits. Having reduced the problem of leader election to one of informing all good processors of a bit held by 1 − o(1) fraction of good processors, we conjecture that the solution to this problem is not possible within polylogarithmic message bounds.Our techniques can be used to provide scalable solutions to Byzantine agreement and other problems.

REFERENCES

• 1: M. Ajtai and N. Linial. The influence of large coalitions. Technical Report 7133(67380), IBM, 1989.
• 2: N. Alon and M. Naor. Coin-flipping games immune against linear-sized coalitions. In Proceedings of the IEEE Foundations of Computer Science (FOCS), 1990.
• 3: Ben-Or, N. Linial, and M. Saks. Collective coin flipping and other models of imperfect randomoness. In Colloq. Math Soc. Janos Bolyai No., 52 Combinatorics, 1987.
• 4: Michael Ben-Or and Nathan Linial. Collective coin flipping and other models of imperfect randomness. In Proceedings of the IEEE Foundations of Computer Science (FOCS), 1985.
• 5: Michael Ben-Or and Nathan Linial. Collective coin flipping. Advances in Computing Research, pages 91115, 1989. JAI Press; Silvio Micali, editor.
• 6: R. Boppana and B. Narayanan. Collective coin flipping and leader election with optimal immunity. manuscript.
• 7: Ravi B. Boppana , Babu O. Narayanan, The biased coin problem, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.252-257, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167164]
• 8: G Bracha, An O(lg n) expected rounds randomized Byzantine generals protocol, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.316-326, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22180]
• 9: Jason Cooper and Nathan Linial. Fast perfect-information leader-election protocol with linear immunity. Combinatorica, 15:319--332, 1995.
• 10: D. Dolev, M. Fischer, R. Fowler, N. Lynch, and H. Strong. An efficient algorithm for byzantine agreement without authentication. Information and Control, 1982.
• 11: Cynthia Dwork , David Peleg , Eli Upfal, Fault tolerance in networks of bounded degree, SIAM Journal on Computing, v.17 n.5, p.975-988, October 1988 [doi>10.1137/0217061]
• 12: Uriel Feige, Noncryptographic Selection Protocols, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.142, October 17-18, 1999
• 13: J. Kahn, G. Kalai, and N. Linial. The influence of random variables on boolean functions. In Proceedings of 29th IEEE Foundations of Computer Science(FOCS), 1988.
• 14: N. Linial. Games computers play: Game-theoretic aspects of computing. Technical report, Hebrew University of Jerusalem, 1992.
• 15: 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]
• 16: 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]
• 17: Alexander Russell , David Zuckerman, Perfect Information Leader Election in log^* n + O(1) Rounds, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.576, November 08-11, 1998
• 18: 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]
• 19: 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.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

General Terms:
Algorithms, Theory