Conditions on input vectors for consensus solvability in asynchronous distributed systems

ABSTRACT

This paper introduces and explores a new condition based approach to solve the consensus problem in asynchronous systems. The approach consists of identifying sets of input vectors, called conditions, for which it is possible to design a protocol solving consensus despite the occurrence of up to f process crashes.The first main result is a generic consensus protocol for the shared memory model. It always guarantees agreement, and also termination (at least) when the inputs satisfy the condition with which the protocol has been instantiated, or when there are no crashes. Then, two particular realistic conditions are defined, and proved to be maximal.The second main result is a characterization of the conditions that allow to solve consensus. The consensus protocol works for any such condition. An efficient version of the protocol is then designed for the message passing model that works when f\geq, and it is shown that no such protocol exists when f\geq n/2. It is also shown how the protocol's safety can be traded for its liveness.

REFERENCES

• 1: Yehuda Afek , Hagit Attiya , Danny Dolev , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Journal of the ACM (JACM), v.40 n.4, p.873-890, Sept. 1993 [doi>10.1145/153724.153741]
• 2: Marcos Kawazoe Aguilera , Sam Toueg, Failure Detection and Randomization: A Hybrid Approach to Solve Consensus, SIAM Journal on Computing, v.28 n.3, p.890-903, Feb. 1999 [doi>10.1137/S0097539796312915]
• 3: James Aspnes, Fast deterministic consensus in a noisy environment, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.299-308, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343631]
• 4: Hagit Attiya, Efficient and robust sharing of memory in message-passing systems, Journal of Algorithms, v.34 n.1, p.109-127, Jan. 2000 [doi>10.1006/jagm.1999.1025]
• 5: Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Journal of the ACM (JACM), v.42 n.1, p.124-142, Jan. 1995 [doi>10.1145/200836.200869]
• 6: Hagit Attiya , Ophir Rachman, Atomic Snapshots in O (n log n) Operations, SIAM Journal on Computing, v.27 n.2, p.319-340, April 1998 [doi>10.1137/S0097539795279463]
• 7: Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
• 8: Yonatan Aumann, Efficient asynchronous consensus with the weak adversary scheduler, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.209-218, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259441]
• 9: 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]
• 10: Ofer Biran , Shlomo Moran , Shmuel Zaks, Deciding 1-solvability of distributed task is NP-hard (extended abstract), Proceedings of the 16th international workshop on Graph-theoretic concepts in computer science, p.206-220, May 1991, Berlin, Germany
• 11: Ofer Biran , Shlomo Moran , Shumuel Zaks, A combinatorial characterization of the distributed 1-solvable tasks, Journal of Algorithms, v.11 n.3, p.420-440, Sep. 1990 [doi>10.1016/0196-6774(90)90020-F]
• 12: E. Borowsky , E. Gafni , N. Lynch , S. Rajsbaum, The BG distributed simulation algorithm, Distributed Computing, v.14 n.3, p.127-146, October, 2001 [doi>10.1007/PL00008933]
• 13: Gabriel Bracha , Sam Toueg, Asynchronous consensus and broadcast protocols, Journal of the ACM (JACM), v.32 n.4, p.824-840, Oct. 1985 [doi>10.1145/4221.214134]
• 14: Tushar Deepak Chandra , Sam Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM (JACM), v.43 n.2, p.225-267, March 1996 [doi>10.1145/226643.226647]
• 15: Soma Chaudhuri, More choices allow more faults: set consensus problems in totally asynchronous systems, Information and Computation, v.105 n.1, p.132-158, July 1993 [doi>10.1006/inco.1993.1043]
• 16: Danny Dolev , Cynthia Dwork , Larry Stockmeyer, On the minimal synchronism needed for distributed consensus, Journal of the ACM (JACM), v.34 n.1, p.77-97, Jan. 1987 [doi>10.1145/7531.7533]
• 17: Danny Dolev , Nancy A. Lynch , Shlomit S. Pinter , Eugene W. Stark , William E. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM (JACM), v.33 n.3, p.499-516, July 1986 [doi>10.1145/5925.5931]
• 18: Cynthia Dwork , Nancy Lynch , Larry Stockmeyer, Consensus in the presence of partial synchrony, Journal of the ACM (JACM), v.35 n.2, p.288-323, April 1988 [doi>10.1145/42282.42283]
• 19: Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985 [doi>10.1145/3149.214121]
• 20: [20] Gafni E., Distributed Computing: a Glimmer of a Theory. in Handbook of Computer Science, (M. Attalah Ed.), CRC Press, 1998.
• 21: Eli Gafni , Elias Koutsoupias, Three-Processor Tasks Are Undecidable, SIAM Journal on Computing, v.28 n.3, p.970-983, Feb. 1999 [doi>10.1137/S0097539796305766]
• 22: Vassos Hadzilacos , Sam Toueg, Fault-tolerant broadcasts and related problems, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 23: Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991 [doi>10.1145/114005.102808]
• 24: Maurice Herlihy , Sergio Rajsbaum, The decidability of distributed decision tasks (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.589-598, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258652]
• 25: Maurice Herlihy , Sergio Rajsbaum, New Perspectives in Distributed Computing, Proceedings of the 24th International Symposium on Mathematical Foundations of Computer Science, p.170-186, September 06-10, 1999
• 26: Maurice P. Herlihy , Jeannette M. Wing, Linearizability: a correctness condition for concurrent objects, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.3, p.463-492, July 1990 [doi>10.1145/78969.78972]
• 27: Prasad Jayanti , Tushar Deepak Chandra , Sam Toueg, Fault-tolerant wait-free shared objects, Journal of the ACM (JACM), v.45 n.3, p.451-500, May 1998 [doi>10.1145/278298.278305]
• 28: Leslie Lamport, The part-time parliament, ACM Transactions on Computer Systems (TOCS), v.16 n.2, p.133-169, May 1998 [doi>10.1145/279227.279229]
• 29: [29] Loui M. C., and Abu-Amara H. H., Memory Requirements for Agreement Among Unreliable Asynchronous Processes. Parallel and Distributed Computing: vol. 4 of Advances in Computing Research, JAI Press, 4:163-183, Greenwich (USA), 1987.
• 30: N. Lynch, A hundred impossibility proofs for distributed computing, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.1-28, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72982]
• 31: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 32: S. Moran , Y. Wolfstahl, Extended impossibility results for asynchronous complete networks, Information Processing Letters, v.26 n.3, p.145-151, Nov. 23, 1987 [doi>10.1016/0020-0190(87)90052-4]
• 33: Yoram Moses , Sergio Rajsbaum, The unified structure of consensus: a layered analysis approach, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.123-132, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277720]
• 34: [34] Mostefaoui A., Rajsbaum S. and Raynal M., Conditions on Input Vectors for Consensus Solvability in Asynchronous Distributed Systems. Research Report #1355, IRISA, University of Rennes, France, October 2000, 27 pages. http://www.irisa.fr/bibli/publi/pi/2000/1355/1355.html.
• 35: Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal , Matthieu Roy, A hierarchy of conditions for consensus solvability, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.151-160, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384006]
• 36: [36] Mostefaoui A., Rajsbaum S., Raynal M. and Roy M., Condition-Based Protocols for Set Agreement Problems. Research Report #1393, IRISA, University of Rennes, France, April 2001, 21 pages. http://www.irisa.fr/bibli/publi/pi/2001/1393/1393.html.
• 37: Achour Mostéfaoui , Michel Raynal, Solving Consensus Using Chandra-Toueg's Unreliable Failure Detectors: A General Quorum-Based Approach, Proceedings of the 13th International Symposium on Distributed Computing, p.49-63, September 27-29, 1999
• 38: Achour Mostefaoui , Michel Raynal , Frederic Tronel, The Best of Both Worlds: A Hybrid Approach to Solve Consensus, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.513-522, June 25-28, 2000
• 39: M. Raynal, Real-time dependable decisions in timed asynchronous distributed systems, Proceedings of the 3rd Workshop on Object-Oriented Real-Time Dependable Systems - (WORDS '97), p.283, February 05-07, 1997

INDEX TERMS

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

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

  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Distributed systems

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Performance, Theory, Verification

Keywords:
asynchronous systems, consensus, fault-tolerance