Randomized Byzantine Agreements

ABSTRACT

Randomized algorithms for reaching Byzantine Agreement were recently proposed in [Rabi83]. With these algorithms, agreement is reached within an expected number of phases that is a small constant independent of the number of processes n and the number of faulty processes t. The algorithms in [Rabi83] tolerate up to [(n-1)/10] faulty processes in asynchronous systems, and up to [(n-1)/4] faulty processes in synchronous systems. In this paper, using the same computation model as in [Rabi83], we describe algorithms that overcome up to [(n-1)/3] faulty processes in asynchronous systems, and up to [(n-1)/2] faulty processes in synchronous systems. With both proposed algorithms, agreement is reached within an expected number of phases that is a small constant independent of n and t, but the communication complexity is higher than in [Rabi83]. It is also shown that no Byzantine Agreement algorithm can overcome more than [(n-1)/3] faulty processes in asynchronous authenticated systems, and hence the asynchronous algorithm proposed here is optimal in this respect.

REFERENCES

• 1: 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]
• 2: Gabriel Bracha , Sam Toueg, Resilient consensus protocols, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.12-26, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806706]
• 3: 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]
• 4: D. Dolev, Unanimity in an unknown and unreliable environment, Proc. 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, pp. 159-168, Oct. 1981.
• 5: D. Dolev, The Byzantine Generals strike again, Journal of Algorithms, Vol. 3, pp. 14-30, 1982.
• 6: Danny Dolev , H. Raymond Strong, Polynomial algorithms for multiple processor agreement, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.401-407, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802215]
• 7: D. Dolev and H. R. Strong, Authenticated algorithms for Byzantine Agreement, SIAM J. Comput., vol. 12, no. 4, pp. 656-666, Nov. 1983.
• 8: 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]
• 9: Leslie Lamport , Robert Shostak , Marshall Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.3, p.382-401, July 1982 [doi>10.1145/357172.357176]
• 10: N. Lynch, M. Fischer, and R. Fowler, A simple and efficient Byzantine Generals algorithm, Proc. Second IEEE Symposium on Reliability in Distributed Software and Data Base Systems, Pittsburgh, Pennsylvania, pp. 46-52, 1982.
• 11: 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]
• 12: Kenneth J. Perry, Randomized Byzantine Agreement, Cornell University, Ithaca, NY, 1984
• 13: K. J. Perry and S. Toueg, An authenticated Byzantine Generals algorithm with early stopping, Technical Report, Cornell University, June 1984.
• 14: M. Rabin, Randomized Byzantine generals, Proc. 24th Symposium on Foundations of Computer Science, Tucson, Arizona, pp. 403-409, Nov. 1983.
• 15: Adi Shamir, How to share a secret, Communications of the ACM, v.22 n.11, p.612-613, Nov. 1979 [doi>10.1145/359168.359176]
• 16: T. K. Srikanth and S. Toueg, Byzantine Agreement made simple: Simulating authentication without signatures, Technical Report in preparation.
• 17: R. Turpin and B. C. Coan, Extenting binary Byzantine Agreement to multivalued Byzantine Agreement, Information Processing Letters, Vol. 18, pp. 73-76, Feb. 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Theory