Byzantine agreement in the full-information model in O(log n) rounds

ABSTRACT

We present a randomized Byzantine Agreement (BA) protocol with an expected running time of O(log n) rounds, in a synchronous full-information network of n players. For any constant ε > 0, the constructed protocol tolerates t non-adaptive Byzantine faults, as long as n ≥ (4 + ε)t. In the full-information model, no restrictions are placed on the computational power of the faulty players or the information available to them. In particular, the faulty players may be infinitely powerful, and they can observe all communication among the honest players.This constitutes significant progress over the best known randomized BA protocol in the same setting which has a round-complexity of Θ(t/log n) rounds [9], and answers an open problem posed by Chor and Dwork [10].

REFERENCES

• 1: Miklós Ajtai and Nathan Linial. The influence of large coalitions. Combinatorica, 13(2):129--145, 1993.
• 2: 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]
• 3: 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]
• 4: Michael BenOr and Nathan Linial. Collective coin flipping, robust voting schemes and minima of banzhaf values. In FOCS, pages 408--416, 1985.
• 5: Piotr Berman , Juan A. Garay, Asymptotically Optimal Distributed Consensus (Extended Abstract), Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.80-94, July 11-15, 1989
• 6: Piotr Berman , Juan A. Garay , Kenneth J. Perry, Optimal Early Stopping in Distributed Consensus (Extended Abstract), Proceedings of the 6th International Workshop on Distributed Algorithms, p.221-237, November 02-04, 1992
• 7: 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]
• 8: Gabriel Bracha, An O(log n) expected rounds randomized byzantine generals protocol, Journal of the ACM (JACM), v.34 n.4, p.910-920, Oct. 1987 [doi>10.1145/31846.42229]
• 9: Benny Chor and Brian A. Coan. A simple and efficient randomized byzantine agreement algorithm. IEEE Trans. Software Eng., 11(6):531--539, 1985.
• 10: Benny Chor and Cynthia Dwork. Randomization in byzantine agreement. Advances in Computing Research, 5:443--497, 1989.
• 11: Cynthia Dwork , Larry Stockmeyer, Flipping persuasively in constant time, SIAM Journal on Computing, v.19 n.3, p.472-499, June 1990 [doi>10.1137/0219032]
• 12: Uriel Feige, Noncryptographic Selection Protocols, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.142, October 17-18, 1999
• 13: Pesech Feldman , Silvio Micali, An Optimal Probabilistic Protocol for Synchronous Byzantine Agreement, SIAM Journal on Computing, v.26 n.4, p.873-933, Aug. 1997 [doi>10.1137/S0097539790187084]
• 14: Michael J. Fischer and Nancy A. Lynch. A lower bound for the time to assure interactive consistency. Inf. Process. Lett., 14(4):183--186, 1982.
• 15: Juan A. Garay , Yoram Moses, Fully Polynomial Byzantine Agreement for Processors in Rounds, SIAM Journal on Computing, v.27 n.1, p.247-290, Feb. 1998 [doi>10.1137/S0097539794265232]
• 16: 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]
• 17: Shafi Goldwasser, Elan Pavlov, and Vinod Vaikuntanathan. Better byzantine agreement protocols in the full-information model. Manuscript, 2006.
• 18: Jeff Kahn, Gil Kalai, and Nathan Linial. The influence of variables on boolean functions. In Proc. 29-th Annual Symposium on Foundations of Computer Science, pages 68--80, 1988.
• 19: Anna Karlin and Andrew Chi-Chih Yao. Probabilistic lower bounds for byzantine agreement. Manuscript, 1986.
• 20: M. Pease , R. Shostak , L. Lamport, Reaching Agreement in the Presence of Faults, Journal of the ACM (JACM), v.27 n.2, p.228-234, April 1980 [doi>10.1145/322186.322188]
• 21: Michael O. Rabin. Randomized byzantine generals. FOCS, pages 403--409, 1983.
• 22: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.0 GENERAL

General Terms:
Algorithms, Theory

Keywords:
byzantine agreement, full-information model