IEEE Transactions on Computers · 2004 · 54 citations · 21 references
ComputingComputer EngineeringComputer ScienceDistributed SystemsFault-tolerant ComputingFault-tolerant SystemsFailure DetectionReliable Distributed SystemsReliable System DesignAccuracyDetectorsFailure DetectorsFault-tolerant Distributed AlgorithmsFault-tolerant Distributed SystemsPartial SynchronySynchronous Distributed Algorithms
Unreliable failure detectors were proposed by Chandra and Toueg as mechanisms that provide information about process failures. Chandra and Toueg defined eight classes of failure detectors, depending on how accurate this information is, and presented an algorithm implementing a failure detector of one of these classes in a partially synchronous system. This algorithm is based on all-to-all communication and periodically exchanges a number of messages that is quadratic on the number of processes. We study the implementability of different classes of failure detectors in several models of partial synchrony. We first show that no failure detector with perpetual accuracy (namely, P, Q, S, and W) can be implemented in these models in systems with even a single failure. We also show that, in these models of partial synchrony, it is necessary a majority of correct processes to implement a failure detector of the class /spl theta/ proposed by Aguilera et al. Then, we present a family of distributed algorithms that implement the four classes of unreliable failure detectors with eventual accuracy (namely, /spl diams/P, /spl diams/Q, /spl diams/S, and /spl diams/W). Our algorithms are based on a logical ring arrangement of the processes, which defines the monitoring and failure information propagation pattern. The resulting algorithms periodically exchange at most a linear number of messages.
21
Unreliable failure detectors for reliable distributed systems
Tushar Chandra, Sam Toueg · Journal of the ACM · 1996 · 2.5K citations · Full text
Reaching Agreement in the Presence of Faults
Marshall C. Pease, Robert E. Shostak, Leslie Lamport · Journal of the ACM · 1980 · 2.4K citations · Full text
Consensus in the presence of partial synchrony
Cynthia Dwork, Nancy Lynch, Larry Stockmeyer · Journal of the ACM · 1988 · 1.9K citations · Full text
The weakest failure detector for solving consensus
Tushar Chandra, Vassos Hadzilacos, Sam Toueg · Journal of the ACM · 1996 · 873 citations · Full text