Irreducibility and additivity of set agreement-oriented failure detector classes

ABSTRACT

Solving agreement problems (such as consensus and k-set agreement) in asynchronous distributed systems prone to process failures has been shown to be impossible. To circumvent this impossibility, distributed oracles (also called unreliable failure detectors) have been introduced. A failure detector provides information on failures, and a failure detector class is defined by a set of abstract properties that encapsulate (and hide) synchrony assumptions. Some failure detector classes have been shown to be the weakest to solve some agreement problems (e.g., Ω is the weakest class of failure detectors that allow solving the consensus problem in asynchronous systems where a majority of processes do not crash).This paper considers several failure detector classes and focuses on their additivity or their irreducibility. It mainly investigates two families of failure detector classes (denoted ◊ S_x and ◊ φ^y, 0≤ x, y ≤ n), shows that they can be "added" to provide a failure detector of the class Ω^z (a generalization of Ω). It also characterizes the power of such an "addition", namely, ◊ S_x + ◊ φ^y ➝ Ω^z ⇔ x+y+z>t+1, where t is the maximum number of processes that can crash in a run. As an example, the paper shows that, while ◊ S_t allows solving 2-set agreement (and not consensus) and ◊ φ¹ allows solving t-set agreement (but not (t-1)-set agreement), their "addition" allows solving consensus. More generally, the paper studies the failure detector classes ◊ S_x, ◊ φ^y and Ω^z, and shows which reductions among these classes are possible and which are not. The paper presents also an Ω^k-based k-set agreement protocol. In that sense, it can be seen as a step toward the characterization of the weakest failure detector that allows solving the k-set agreement problem.

REFERENCES

• 1: 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]
• 2: 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]
• 3: 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]
• 4: 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 ]
• 5: 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 ]
• 6: Delporte-Gallet C., Fauconnier H. and Guerraoui R., (Almost) All Objects are Universal in Message Passing Systems. Proc. 19th Symp. on Distributed Computing (DISC'05) Springer Verlag LNCS #3724, pp. 184--198, 2005.
• 7: 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]
• 8: 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]
• 9: Vassos Hadzilacos , Sam Toueg, Fault-tolerant broadcasts and related problems, Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993
• 10: Herlihy M. P. and Penso L. D., Tight Bounds for k-Set Agreement with Limited Scope Accuracy Failure Detectors. Distributed Computing 18(2):157--166, 2005.
• 11: 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]
• 12: 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]
• 13: 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]
• 14: Achour Mostefaoui , Sergio Rajsbaum , Michel Raynal, The combined power of conditions and failure detectors to solve asynchronous set agreement, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073848]
• 15: Mostefaoui A., Rajsbaum S., Raynal M. and Travers C., From ◊ ω to Ω: a Simple Bounded Quiescent Reliable broadcast-based Transformation. Tech Report 1759 IRISA, University of Rennes 1 (France), 2005.
• 16: Mostefaoui A., Rajsbaum S., Raynal M. and Travers C., Irreducibility and Additivity of Set Agreement-oriented Failure Detector Classes. Tech Report 1758 IRISA, University of Rennes 1 (France), 2005. ftp://ftp. irisa. fr/techreports/2005/PI-1758. ps. gz.
• 17: 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
• 18: 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]
• 19: Mostefaoui A. and Raynal M., Leader-Based Consensus. Parallel Processing Letters 11(1):95--107, 2001.
• 20: Gil Neiger, Failure detectors and the wait-free hierarchy (extended abstract), Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.100-109, August 20-23, 1995, Ottowa, Ontario, Canada [doi>10.1145/224964.224976]
• 21: Michel Reynal, A short introduction to failure detectors for asynchronous distributed systems, ACM SIGACT News, v.36 n.1, March 2005 [doi>10.1145/1052796.1052806]
• 22: 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]
• 23: 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]
• 24: 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]

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: Synchronization; Multiprocessing/multiprogramming/multitasking; Concurrency
      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

General Terms:
Algorithms, Reliability, Theory

Keywords:
asynchronous system, fault-tolerance, unreliable failure detector