Early stopping in Byzantine agreement

ABSTRACT

Two different kinds of Byzantine Agreement for distributed systems with processor faults are defined and compared. The first is required when coordinated actions may be performed by each participant at different times. This kind is called Simultaneous Byzantine Agreement (SBA). This paper deals with the number of rounds of message exchange required to reach Byzantine Agreement of either kind (BA). If an algorithm allows its participants to reach Byzantine agreement in every execution in which at most t participants are faulty, then the algorithm is said to tolerate t faults. It is well known that any BA algorithm that tolerates t faults (with t < n - 1 where n denotes the total number of processors) must run at least t + 1 rounds in some execution. However, it might be supposed that in executions where the number f of actual faults is small compared to t, the number of rounds could be correspondingly small. A corollary of our first result states that (when t < n - 1) any algorithm for SBA must run t + 1 rounds in some execution where there are no faults. For EBA (with t < n - 1), a lower bound of min(t + 1,f + 2) rounds is proved. Finally, an algorithm for EBA is presented that achieves the lower bound, provided that t is on the order of the square root of the total number of processors.

REFERENCES

• 1: Brian A Coan, A communication-efficient canonical form for fault-tolerant distributed protocols, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.63-72, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10596]
• 2: CRISTIAN, F., AGHILI, H., STRONG, R., AND DOLEV, D. Atomic broadcast: from simple message diffusion to Byzantine agreement. In Proceedings of of the 15th International Conference on Fault Tolerant Computing (June). 1985, pp. 1-7.
• 3: 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]
• 4: DOLEV, D. Unanimity in an unknown and unreliable environment. In Proceedings of the 22nd IEEE Annual Symposium on Foundations of Computer Science. IEEE, New York, 1981, pp. 159-168.
• 5: DOLEV, D. The Byzantine generals strike again. J. Algor. 3 (1982), 14-30.
• 6: DOLEV, D., FISCHER, M., FOWLER, R., LYNCH, N., AND STRONG, R. An efficient algorithm for Byzantine agreement without authentication. Inf. Control 3 (1983), 257-274.
• 7: Danny Dolev , Rüdiger Reischuk, Bounds on information exchange for Byzantine agreement, Journal of the ACM (JACM), v.32 n.1, p.191-204, Jan. 1985 [doi>10.1145/2455.214112]
• 8: DOLLY, D., RIESCHUK, R., AND STRONG, R. 'Eventual" is earlier than 'Immediate'. In Proceedings of the 23rd IEEE Annual Symposium on Foundations of Computer Science. IEEE, New York, 1982, pp. 196-203.
• 9: 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]
• 10: DOLEV, D., AND STRONG, H.R. Distributed commit with bounded waiting. In Proceedings of the 2nd Symposium on Reliability in Distributed Software and Database Systems (Pittsburgh, Pa., July). 1982, pp. 53-60.
• 11: DOLEV, D., AND STRONG, H. R. Requirements for agreement in a distributed system. In Proceedings of the 2nd International Symposium on Distributed Data Bases (Sept.). 1982, pp. 115-129.
• 12: DOLEV, O., AND STRONG, H. R. Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12 (i983), 656-666.
• 13: C Dwork , Y Moses, Knowledge and common knowledge in a Byzantine environment I: crash failures, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.149-169, March 1986, Monterey, California, United States
• 14: FISCHER, M., FOWLER, R., AND LYNCH, N. A simple and efficient Byzantine generals algorithm. In Proceedings of the 2nd Symposium on Reliability in Distributed Software and Database Systems (Pittsburgh, Pa., July). 1982, pp. 46-52.
• 15: FISCHER, M., AND LYNCH, N. A lower bound for the time to assure interactive consistency. Inf. Process. Lett. 14 (1982), 183-186.
• 16: 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]
• 17: Leslie Lamport, Using Time Instead of Timeout for Fault-Tolerant Distributed Systems., ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.2, p.254-280, April 1984 [doi>10.1145/2993.2994]
• 18: Leslie Lamport , P. M. Melliar-Smith, Synchronizing clocks in the presence of faults, Journal of the ACM (JACM), v.32 n.1, p.52-78, Jan. 1985 [doi>10.1145/2455.2457]
• 19: 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]
• 20: MOSES, Y., AND WAARTS, O. Coordinated traversal: (t + l)-round Byzantine agreement in polynomial time. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science. IEEE, New York, 1988.
• 21: 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]
• 22: Fred B. Schneider, Byzantine generals in action: implementing fail-stop processors, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.145-154, May 1984 [doi>10.1145/190.357399]
• 23: SRIKANTH, T., AND TOUEG, S. Byzantine agreement made simple: Simulating authentication without signatures. Dist. Comput. 2 (1987), 80-94.
• 24: Sam Toueg , Kenneth J. Perry , T. K. Srikanth, Fast distributed agreement, SIAM Journal on Computing, v.16 n.3, p.445-457, June 1987 [doi>10.1137/0216031]

INDEX TERMS

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

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

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Performance, Reliability, Theory, Verification