Fast quantum byzantine agreement

ABSTRACT

We present a fast quantum Byzantine Agreement protocol that can reach agreement in O(1) expected communication rounds against a strong full information, dynamic adversary, tolerating up to the optimal t‹n3 faulty players in the synchronous setting, and up to t‹n4 faulty players for asynchronous systems. This should be contrasted with the known classical synchronous lower bound of Ω(√ nlog n) [3] when t=(n).

REFERENCES

• 1: D. Aharonov , M. Ben-Or, Fault-tolerant quantum computation with constant error, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.176-188, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258579]
• 2: James Aspnes, Lower bounds for distributed coin-flipping and randomized consensus, Journal of the ACM (JACM), v.45 n.3, p.415-450, May 1998 [doi>10.1145/278298.278304]
• 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: M. Ben-Or and E. Pavlov, unpublished manuscript.
• 6: 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]
• 7: 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]
• 8: Benny Chor and Brian A. Coan, "A Simple and Efficient Randomized Byzantine Agreement Algorithm," IEEE Trans. Software Eng. 11(6): 531--539, 1985.
• 9: 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]
• 10: Claude Crépeau , Daniel Gottesman , Adam Smith, Secure multi-party quantum computation, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510000]
• 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: 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]
• 13: Juan A. Garay , Yoram Moses, Fully polynomial Byzantine agreement in t + 1 rounds, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.31-41, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167101]
• 14: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 15: 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]
• 16: M. O. Rabin, "Randomized Byzantine Generals," In Proceedings of the 24th Annual IEEE Symposyum on the Foundations of Computer Science, IEEE, pp. 403--409, 1983.

INDEX TERMS

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

General Terms:
Theory

Keywords:
Byzantine agreement, quantum computation