Asynchronous Byzantine consensus

ABSTRACT

Reaching agreement in an asynchronous environment is essential to guarantee consistency in distributed data processing. All previous asynchronous protocols were either probabilistic or they assumed a fail-stop mode of failure. The deterministic protocol presented in this paper reaches a Strong Byzantine Agreement in a system of asynchronous processors; and therefore can sustain arbitrary faults. In our model, processors can be completely asynchronous, though the communication network has the property that a message being sent by a correctly operating processor to a set of processors will reach its destinations within a predetermined period &Dgr;. Additional results presented in the paper prove that in the above model one cannot reach a consensus within a bounded time. A correctly operating processor should wait to receive messages from other processors before making a decision. This result holds also for Weak Byzantine Agreement, but not for nontrivial consensus. We present a trivial protocol to reach a nontrivial consensus in bounded time.

REFERENCES

• 1: H. Aghili, M. Astrahan, S. Finkelstein, W. Kim, J. McPherson, M. Schkolnick and H. R. Strong, A Prototype for a Highly available Database System, IBM Research Report RJ3755, 1983.
• 2: H. Breitwieser and M. Leszak, Improving availability of Partily Redundant Databases by Majority Consensus Protocols, in Distributed Database, H.J. Schneider (ed), North-Holland, 1982.
• 3: D. Dolev, S. Dwork and L. Stockmeyer, On the Minimal Synchronism Needed for Distributed Consensus, proceedings, the 24th Annual Symposium on Foundations of Computer Science, 1983.
• 4: D. Dolev, M. Fischer, R. Fowler, N. Lynch and R. Strong, Efficient Byzantine Agreement Without Authentication, Information and Control 3(1983), pp. 257-274.
• 5: D. Dolev, R. Reischuk, and R. H. Strong, proceedings, the 23rd Annual Symposium on Foundations of Computer Science, 1982.
• 6: D. Dolev and H. R. Strong, Authenticated Algorithms for Byzantine Agreement, Siam Journal on Computing 12(1983), pp. 656-666.
• 7: 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.
• 8: D. Dolev and H. R. Strong, Byzantine Agreements, proceedings, COMPCON83, San Francisco, pp. 77-81, Mar 1983.
• 9: Michael J. Fischer, The Consensus Problem in Unreliable Distributed Systems (A Brief Survey), Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.127-140, August 21-27, 1983
• 10: 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]
• 11: 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]
• 12: 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]
• 13: C. Mohan , R. Strong , S. Finkelstein, Method for distributed transaction commit and recovery using Byzantine Agreement within clusters of processors, Proceedings of the second annual ACM symposium on Principles of distributed computing, p.89-103, August 17-19, 1983, Montreal, Quebec, Canada [doi>10.1145/800221.806712]
• 14: M. O. Rabin, The Choice Coordination Problem, Acta Informatica 17 (1982), pp. 121-134.
• 15: R. Reischuk, A New Solution for the Byzantine Generals Problem, IBM Report RJ3673, November 1982.
• 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]
• 17: Robert H. Thomas, A Majority consensus approach to concurrency control for multiple copy databases, ACM Transactions on Database Systems (TODS), v.4 n.2, p.180-209, June 1979 [doi>10.1145/320071.320076]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Asynchronous/synchronous operation

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Concurrency

General Terms:
Design, Management, Performance