Fast asynchronous byzantine agreement and leader election with full information

ABSTRACT

We resolve two long-standing open problems in distributed computation by describing polylogarithmic protocols for Byzantine agreement and leader election in the asynchronous full information model with a non-adaptive malicious adversary. All past protocols for asynchronous Byzantine Agreement had been exponential, and no protocol for asynchronous leader election had been known.

Our protocols tolerate up to n/6+ε faulty processors, for any positive constant ε. They are Monte Carlo, succeeding with probability 1 - o(1) for Byzantine agreement, and constant probability for leader election. A key technical contribution of our paper is a new approach for emulating Feige's lightest bin protocol, even with adversarial message scheduling.

REFERENCES

• 1: Miklós Ajtai and Nathan Linial. The influence of large coalitions. Combinatorica, 13(2):129--145, 1993.
• 2: Hagit Attiya. Personal communication, 2007.
• 3: Ziv Bar-Joseph , Michael Ben-Or, A tight lower bound for randomized synchronous consensus, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.193-199, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277733]
• 4: Michael Ben-Or, Another advantage of free choice (Extended Abstract): Completely asynchronous agreement protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.27-30, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806707]
• 5: Michael Ben-Or and Nathan Linial. Collective coin flipping. In Silvio Micali, editor, Advances in Computing Research 5: Randomness and Computation, pages 91--115. JAI Press, 1989.
• 6: Michael Ben-Or , Elan Pavlov , Vinod Vaikuntanathan, Byzantine agreement in the full-information model in O(log n) rounds, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132543]
• 7: Piotr Berman and Juan A. Garay. Randomized distributed agreement revisited. In Digest of Papers: FTCS-23, The 23rd Annual International Symposium on Fault-Tolerant Computing, pages 412--419, 1993.
• 8: Gabriel Bracha, An asynchronous [(n - 1)/3]-resilient consensus protocol, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.154-162, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806743]
• 9: Christian Cachin, Klaus Kursawe, and Victor Shoup. Random oracles in constantinople: Practical asynchronous byzantine agreement using cryptography. J. Cryptology, 18(3):219--246, 2005.
• 10: Ran Canetti , Tal Rabin, Fast asynchronous Byzantine agreement with optimal resilience, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.42-51, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167105]
• 11: Benny Chor and Cynthia Dwork. Randomization in Byzantine agreement. In Silvio Micali, editor, Advances in Computing Research 5: Randomness and Computation, pages 443--497. JAI Press, 1989.
• 12: Benny Chor , Michael Merritt , David B. Shmoys, Simple constant-time consensus protocols in realistic failure models, Journal of the ACM (JACM), v.36 n.3, p.591-614, July 1989 [doi>10.1145/65950.65956]
• 13: Uriel Feige, Noncryptographic Selection Protocols, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.142, October 17-18, 1999
• 14: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588060]
• 15: Shafi Goldwasser , Elan Pavlov , Vinod Vaikuntanathan, Fault-Tolerant Distributed Computing in Full-Information Networks, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.15-26, October 21-24, 2006 [doi>10.1109/FOCS.2006.30]
• 16: Ronen Gradwohl, Salil P. Vadhan, and David Zuckerman. Random selection with an adversarial majority. In Advances in Cryptology - CRYPTO 2006, 26th Annual International Cryptology Conference, volume 4117 of Lecture Notes in Computer Science, pages 409--426. Springer, 2006.
• 17: Valerie King , Jared Saia , Vishal Sanwalani , Erik Vee, Scalable leader election, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.990-999, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109667]
• 18: Valerie King , Jared Saia , Vishal Sanwalani , Erik Vee, Towards Secure and Scalable Computation in Peer-to-Peer Networks, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.87-98, October 21-24, 2006 [doi>10.1109/FOCS.2006.77]
• 19: Jesper Buus Nielsen, A Threshold Pseudorandom Function Construction and Its Applications, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.401-416, August 18-22, 2002
• 20: 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]
• 21: 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
• 22: 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]
• 23: Sam Toueg, Randomized Byzantine Agreements, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.163-178, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806744]
• 24: David Zuckerman, Randomness-optimal oblivious sampling, Random Structures & Algorithms, v.11 n.4, p.345-367, Dec. 1997
• 25: David Zuckerman. Personal communication, 2006.