Bounds on information exchange for Byzantine Agreement

ABSTRACT

Byzantine Agreement has become increasingly important in establishing distributed properties when there may exist errors in the systems. Recent polynomial algorithms for reaching Byzantine Agreement provide us with feasible solutions for obtaining coordination and synchronization in distributed systems. In this paper we study the amount of information exchange necessary to ensure Byzantine Agreement. This is measured by the number of messages and the number of signatures appended to messages (in case of authenticated algorithms) the participating processors need to send, in the worse case, in order to reach Byzantine Agreement. The lower bound for the number of signatures in the authenticated case is &Ohgr;(nt), where n is the number of participating processors and t is the upper bound on the number of faults. If n is large compared to t, it matches the upper bounds from previously known algorithms. The lower bound for the number of messages is &Ohgr;(n+t2). We present an algorithm that achieves this bound and for which the number of phases does not exceed the minimum t+1 by more than a constant factor.

REFERENCES

• 1: W. Diffie and M. Hellman, "New direction in cryptography", IEEE Trans. on Inform. IT-22, 6(1976), 644-654.
• 2: Richard A. DeMillo , Nancy A. Lynch , Michael J. Merritt, Cryptographic protocols, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.383-400, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802214]
• 3: D. Dolev, "The Byzantine Generals Strike Again", Journal of Algorithms, vol. 3, no. 1, 1982.
• 4: D. Dolev, "Unanimity in an Unknown and Unreliable Environment", 22nd Annual Symposium on Foundations of Computer Science, pp. 159-168, 1981.
• 5: D. Dolev, M. Fischer, R. Fowler, N. Lynch, and R. Strong, "Efficient Byzantine Agreement Without Authentication", IBM Research Report RJ3428 (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", IBM Research Report RJ3416 (1982).
• 8: D. Dolev and H. R. Strong, "Distributed Commit with Bounded Waiting", Proceedings, Second Symposium on Reliability in Distributed Software and Database Systems, Pittsburgh, July 1982.
• 9: D. Dolev and H. R. Strong, "Requirements for Agreement in a Distributed System", Proceedings, the Second International Symposium on Distributed Data Bases, Berlin, Sep. 1982.
• 10: M. Fischer, R. Fowler, and N. Lynch, "A Simple and Efficient Byzantine Generals Algorithm", Proceedings, Second Symposium on Reliability in Distributed Software and Database Systems, Pittsburgh, July 1982.
• 11: M. Fischer, and L. Lamport, private communication of paper in preparation, April, 1982.
• 12: L. Lamport, The Weak Byzantine Generals Problem, Journal of the ACM (JACM), v.30 n.3, p.668-676, July 1983 [doi>10.1145/2402.322398]
• 13: 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]
• 14: N. Lynch, and M. Fischer, "A Lower Bound for the Time to Assure Interactive Consistency", Information Processing Letters, to appear.
• 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: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Authentication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Performance, Security, Theory