Extracting quorum failure detectors

ABSTRACT

It is well known that the failure detector Ω is necessary and sufficient to solve consensus in asynchronous message passing systems where a majority of processes is guaranteed to be correct [1,2]. But what if the problem were to be solved in an arbitrary environment where any number of processes may fail and at any times? The answer was provided by Delporte et al who showed that a certain quorum failure detector, which they called Σ, is necessary and, together with Ω, sufficient to solve consensus in any environment [4].

Moving beyond consensus and such specific problems, we pose and answer the following general question: Given an arbitrary decision problem P, is it possible to identify a quorum failure detector that is provably necessary to solve P in any environment? We answer this question in the affirmative: we present a universal quorum failure detector Q that, when instantiated with any decision problem P, yields a quorum failure detector that is necessary to solve P in any environment. We demonstrate the power of this universal detector by showing that several existing quorum failure detectors, known to be necessary and sufficient to solve some well-known problems, are obtained by instantiating Q with those problems. In particular, the quorum failure detector Σ proposed for consensus [4], Σ^v proposed for nonuniform consensus [8], and the loneliness detector for (n−1)-set agreement [6] are all obtained by instantiating the universal detector Q with the respective problems. Besides yielding existing failure detectors, Q has led to a new and useful detector: while mutual exclusion can be solved using the Trusting failure detector T when a majority of processes is correct [5], it is not known how to solve this problem in an arbitrary environment. We show that the quorum failure detector Σ^l, obtained by instantiating Q with the mutual exclusion problem, together with T, is sufficient to solve mutual exclusion in any environment. The necessity of Σ^l to solve mutual exclusion is implied by our general theorem.

Our proof of the universality of Q employs a different technique than the common reduction technique introduced by Chandra et al [1], where processes build an infinite DAG of sampled failure detector values and use it for locally simulating runs of the algorithm.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Soma Chaudhuri, Agreement is harder than consensus: set consensus problems in totally asynchronous systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.311-324, August 22-24, 1990, Quebec City, Quebec, Canada [doi>10.1145/93385.93431]
• 4: Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Vassos Hadzilacos , Petr Kouznetsov , Sam Toueg, The weakest failure detectors to solve certain fundamental problems in distributed computing, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011818]
• 5: Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Petr Kouznetsov, Mutual exclusion in asynchronous systems with failure detectors, Journal of Parallel and Distributed Computing, v.65 n.4, p.492-505, April 2005 [doi>10.1016/j.jpdc.2004.11.008]
• 6: Carole Delporte-Gallet , Hugues Fauconnier , Rachid Guerraoui , Andreas Tielmann, The Weakest Failure Detector for Message Passing Set-Agreement, Proceedings of the 22nd international symposium on Distributed Computing, September 22-24, 2008, Arcachon, France [doi>10.1007/978-3-540-87779-0_8]
• 7: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]
• 8: Jonathan Eisler , Vassos Hadzilacos , Sam Toueg, The weakest failure detector to solve nonuniform consensus, 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.1073849]
• 9: 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]
• 10: Prasad Jayanti , Sam Toueg, Every problem has a weakest failure detector, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400763]
• 11: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]

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

General Terms:
Algorithms, Reliability, Theory

Keywords:
asynchronous system, failure detector, fault tolerance, mutual exclusion