The combined power of conditions and failure detectors to solve asynchronous set agreement

ABSTRACT

An approach to cope with the impossibility of solving agreement problems in asynchronous systems made up of n processes and prone to t process crashes is to use failure detectors. An orthogonal approach that has been used is to consider conditions that restrict the possible inputs to such a problem. This paper considers a system with both failure detectors and conditions. The aim is to identify the failure detector class that abstracts away the synchrony needed to solve k-set agreement for a given condition.Three main contributions are presented. The first is a new class of failure detectors denoted Φt^y, 0≤ y≤ t. The processes can invoke a primitive queryy(S) with a set of process ids S. Roughly speaking, queryy(S) returns true only when all processes in S have crashed, provided t-y<|S|≤ t. It is shown that the classic Chandra and Toueg's failure detectors are incomparable to the Φt^y failure detectors. The second contribution is a generic condition-based protocol for Φt^y that solves k-set agreement. It can be instantiated with any (t-d)-legal condition C and solves k-set agreement for k=1+max(0,d-y); termination is guaranteed for inputs in C. (A condition is x-legal if and only if it can be used to solve x-fault tolerant asynchronous consensus.) A variant of the protocol that terminates always is described. Finally, a corresponding lower bound is presented showing that there is no Φt^y-based k-set agreement protocol for (t-d)-legal conditions with k≤ max(0,d-y).

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: 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
• 3: Elizabeth Borowsky , Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.91-100, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167119]
• 4: 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]
• 5: 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]
• 6: 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]
• 7: Soma Chaudhuri , Maurice Erlihy , Nancy A. Lynch , Mark R. Tuttle, Tight bounds for k-set agreement, Journal of the ACM (JACM), v.47 n.5, p.912-943, Sept. 2000 [doi>10.1145/355483.355489]
• 8: Francis Chu, Reducing &OHgr; to ◊W , Information Processing Letters, v.67 n.6, p.289-293, Sept. 30, 1998 [doi>10.1016/S0020-0190(98)00122-7]
• 9: Roberto de Prisco , Dahlia Malkhi , Michael Reiter, On k-Set Consensus Problems in Asynchronous Systems, IEEE Transactions on Parallel and Distributed Systems, v.12 n.1, p.7-21, January 2001 [doi>10.1109/71.899936]
• 10: 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]
• 11: 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]
• 12: 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
• 13: Eli Gafni , Rachid Guerraoui , Bastian Pochon, From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060696]
• 14: Rachid Guerraoui, Indulgent algorithms (preliminary version), Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.289-297, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343630]
• 15: Rachid Guerraoui , Michel Raynal, The Information Structure of Indulgent Consensus, IEEE Transactions on Computers, v.53 n.4, p.453-466, April 2004 [doi>10.1109/TC.2004.1268403]
• 16: Herlihy M.P. and Penso L. D., Tight Bounds for k-Set Agreement with Limited Scope Accuracy Failure Detectors. Proc. 17th Int. Symposium on Distributed Computing (DISC'03), Springer Verlag LNCS #2848, pp. 279--291, Sorrento (Italy), 2003.
• 17: Maurice Herlihy , Sergio Rajsbaum, Algebraic spans, Mathematical Structures in Computer Science, v.10 n.4, p.549-573, August 2000 [doi>10.1017/S0960129500003170]
• 18: 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]
• 19: 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]
• 20: M. Hurfin , A. Mostéfaoui , M. Raynal, A Versatile Family of Consensus Protocols Based on Chandra-Toueg's Unreliable Failure Detectors, IEEE Transactions on Computers, v.51 n.4, p.395-408, April 2002 [doi>10.1109/12.995450]
• 21: Izumi T. and Masuzawa T., Synchronous Condition-Based Consensus Adapting to Input Vector Legality. Proc. 18th Int. Symposium on Distributed Computing (DISC'04), Springer-Verlag LNCS #3224, pp. 16--29, 2004.
• 22: Mostefaoui A., Mourgaya E., and Raynal M., Asynchronous Implementation of Failure Detectors, Proc. Int. IEEE Conference on Dependable Systems and Networks (DSN'03), IEEE Computer Press, pp. 351-360, San Francisco (CA), 2003.
• 23: Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, Conditions on input vectors for consensus solvability in asynchronous distributed systems, Journal of the ACM (JACM), v.50 n.6, p.922-954, November 2003 [doi>10.1145/950620.950624]
• 24: Mostefaoui A., Rajsbaum S. and Raynal M., Using Conditions to Expedite Consensus in Synchronous Systems. Proc. 17th Int. Symposium on Distributed Computing (DISC'03), Springer-Verlag LNCS #2848, pp. 249--263, 2003.
• 25: Mostefaoui A., Rajsbaum S. and Raynal M., The Synchronous Condition-Based Consensus Hierarchy. Proc. 18th Int. Symposium on Distributed Computing (DISC'04), Springer-Verlag LNCS #3224, pp. 1-15, Amsterdam (Netherlands), 2004.
• 26: Mostefaoui A., Rajsbaum S. and Raynal M., The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement. Tech Report #1688, IRISA, Université de Rennes (France), 2005. http://www.irisa.fr/bibli/publi/pi/2005/1688/1688.html
• 27: 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
• 28: Achour Mostéfaoui , Sergio Rajsbaum , Michel Raynal , Matthieu Roy, Condition-based consensus solvability: a hierarchy of conditions and efficient protocols, Distributed Computing, v.17 n.1, p.1-20, February 2004 [doi>10.1007/s00446-003-0093-9]
• 29: 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
• 30: Achour Mostéfaoui , Michel Raynal, k-set agreement with limited accuracy failure detectors, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.143-152, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343536]
• 31: Achour Mostefaoui , Michel Raynal, Randomized k-set agreement, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.291-297, July 2001, Crete Island, Greece [doi>10.1145/378580.378690]
• 32: Mostefaoui A. and Raynal M., Leader-Based Consensus. Parallel Processing Letters, 11(1):95--107, 2001.
• 33: Raïpin Parvédy Ph., Raynal M. and Travers C., Decision Optimal Early-Stopping k-set Agreement in Synchronous Systems with General Omission Failures. Tech Report #1711, IRISA, Université de Rennes (France), 2005. http://www.irisa.fr/bibli/publi/pi/2005/1711/1711.html
• 34: Michel Raynal, Consensus in Synchronous Systems: A Concise Guided Tour, Proceedings of the 2002 Pacific Rim International Symposium on Dependable Computing, p.221, December 16-18, 2002
• 35: Michael Saks , Fotios Zaharoglou, Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge, SIAM Journal on Computing, v.29 n.5, p.1449-1483, March 2000 [doi>10.1137/S0097539796307698]
• 36: André Schiper, Early consensus in an asynchronous system with a weak failure detector, Distributed Computing, v.10 n.3, p.149-157, April 1997 [doi>10.1007/s004460050032]
• 37: Jiong Yang , Gil Neiger , Eli Gafni, Structured derivations of consensus algorithms for failure detectors, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.297-306, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277755]
• 38: Zibin Y., Condition-Based Consensus in Synchronous Systems. Proc. 17th Int. Symposium on Distributed Computing, Springer-Verlag LNCS #2848, pp. 239--248, 2003.

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

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking; Concurrency; Synchronization
      D.4.5 Reliability
          Subjects: Fault-tolerance

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded); Relations between models

General Terms:
Algorithms, Reliability, Theory

Keywords:
asynchronous system, condition, consensus, failure detection, process crash, set agreement, shared memory, snapshot