Conditions on input vectors for consensus solvability in asynchronous distributed systems

ABSTRACT

This article introduces and explores the condition-based approach to solve the consensus problem in asynchronous systems. The approach studies conditions that identify sets of input vectors for which it is possible to solve consensus despite the occurrence of up to f process crashes. The first main result defines acceptable conditions and shows that these are exactly the conditions for which a consensus protocol exists. Two examples of realistic acceptable conditions are presented, and proved to be maximal, in the sense that they cannot be extended and remain acceptable. The second main result is a generic consensus shared-memory protocol for any acceptable condition. The protocol always guarantees agreement and validity, and terminates (at least) when the inputs satisfy the condition with which the protocol has been instantiated, or when there are no crashes. An efficient version of the protocol is then designed for the message passing model that works when f < n/2, and it is shown that no such protocol exists when f ≥ 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 , Zvi Avidor, Wait-Free n-Set Consensus When Inputs Are Restricted, Proceedings of the 16th International Conference on Distributed Computing, p.326-338, October 28-30, 2002
• 5: 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]
• 6: 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]
• 7: 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]
• 8: Jennifer L. Welch , Hagit Attiya, Distributed computing: fundamentals, simulations and advanced topics, McGraw-Hill, Inc., Hightstown, NJ, 1998
• 9: 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]
• 10: Yossi Azar , Andrei Z. Broder , Mark S. Manasse, On-line choice of on-line algorithms, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.432-440, January 25-27, 1993, Austin, Texas, United States
• 11: 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]
• 12: Piotr Berman , Juan A. Garay, Adaptability and the Usefulness of Hints (Extended Abstract), Proceedings of the 6th Annual European Symposium on Algorithms, p.271-282, August 24-26, 1998
• 13: 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]
• 14: 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
• 15: 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]
• 16: Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992 [doi>10.1145/146370.146381]
• 17: Tushar Deepak Chandra , Vassos Hadzilacos , Sam Toueg, The weakest failure detector for solving consensus, Journal of the ACM (JACM), v.43 n.4, p.685-722, July 1996 [doi>10.1145/234533.234549]
• 18: 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]
• 19: 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]
• 20: 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]
• 21: 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]
• 22: 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]
• 23: 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]
• 24: Roy Friedman , Achour Mostéfaoui , Sergio Rajsbaum , Michel Raynal, Distributed Agreement and Its Relation with Error-Correcting Codes, Proceedings of the 16th International Conference on Distributed Computing, p.63-87, October 28-30, 2002
• 25: Gafni, E. 1998. Distributed Computing: a Glimmer of a Theory, in Handbook of Computer Science. CRC Press.
• 26: 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]
• 27: Rachid Guerraoui, Revistiting the Relationship Between Non-Blocking Atomic Commitment and Consensus, Proceedings of the 9th International Workshop on Distributed Algorithms, p.87-100, September 13-15, 1995
• 28: Rachid GUERRAOUI , Michel Raynal, A Generic Framework for Indulgent Consensus, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.88, May 19-22, 2003
• 29: Vassos Hadzilacos , Sam Toueg, Fault-tolerant broadcasts and related problems, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 30: 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]
• 31: 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]
• 32: 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
• 33: Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999 [doi>10.1145/331524.331529]
• 34: 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]
• 35: 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]
• 36: 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]
• 37: Loui, M., and Abu-Amara, H. 1987. Memory Requirements for Agreement Among Unreliable Asynchronous Processes, in Parallel and Distributed Computing (Greenwich, Conn.). Advances in Computing Research, vol. 4. JAI Press.
• 38: 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]
• 39: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 40: 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]
• 41: Yoram Moses , Sergio Rajsbaum, A Layered Analysis of Consensus, SIAM Journal on Computing, v.31 n.4, p.989-1021, 2002 [doi>10.1137/S0097539799364006]
• 42: Mostefaoui, A., Mourgaya, E., Raipin, P., and Raynal, M. 2003. Evaluating the condition-based approach to solve consensus. In Proceedings of the International Conference on Dependable Systems and Networks (DSN03) (San Francisco, Calif.). IEEE Computer Society Press, Los Alamitos, Calif., 541--550.
• 43: Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.153-162, July 2001, Hersonissos, Greece [doi>10.1145/380752.380792]
• 44: Achour Mostéfaoui , Sergio Rajsbaum , Michel Raynal, A Versatile and Modular Consensus Protoco, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.364-373, June 23-26, 2002
• 45: Mostefaoui, A., Rajsbaum, S., and Raynal, M. 2003. Using conditions to expedite consensus in synchronous distributed systems. In Proceedings of the 17th International Symposium on Distributed Computing (DISC'03) (Sorrento, Italy). Lecture Notes in Computer Science, vol. 2848. Springer-Verlag, New York, 249--263.
• 46: Mostefaoui, A., Rajsbaum, S., Raynal, M., and Roy, M. 2001a. Efficient condition-based consensus. In Proceedings of the 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO 8) (Catalonia, Spain). Carleton Univ. Press, 275--292.
• 47: 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]
• 48: Achour Mostéfaoui , Sergio Rajsbaum , Michel Raynal , Matthieu Roy, Condition-Based Protocols for Set Agreement Problems, Proceedings of the 16th International Conference on Distributed Computing, p.48-62, October 28-30, 2002
• 49: 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
• 50: 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
• 51: 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
• 52: Gadi Taubenfeld , Shmuel Katz , Shlomo Moran, Impossibility results in the presence of multiple faulty processes, Information and Computation, v.113 n.2, p.173-198, Sept. 1994 [doi>10.1006/inco.1994.1068]
• 53: Gadi Taubenfeld , Shlomo Moran, Possibility and impossibility results in a shared memory environment, Acta Informatica, v.33 n.1, p.1-20, 1996 [doi>10.1007/s002360050034]
• 54: Zibin, Y. 2003. Condition-based consensus in synchronous systems. In Proceedings of the 17th International Symposium on Distributed Computing (DISC'03) (Sorrento, Italy). Lecture Notes in Computer Science, vol. 2848. Springer-Verlag, New York, 239--248.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability; Fault tolerance

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Fault-tolerance

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Computability theory; Relations between models
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency; Alternation and nondeterminism
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Performance, Reliability, Theory

Keywords:
Asynchronous systems, atomic registers, consensus problem, crash failures, fault-tolerance, message-passing, shared memory