Eventually perfect failure detector
An eventually perfect failure detector eventually and permanently suspects every crashed process at every correct process and eventually stops false suspicions among correct processes.
Class diamond-P combines strong completeness with eventual strong accuracy. After some finite time, correct processes are never suspected by correct processes; that time need not be known to an observer. Correct means never crashing in the modeled crash-stop run. [1]
Unlike a perfect detector, this class permits initial false suspicions. Its contract does not prescribe a bounded warm-up duration, a numerical detection deadline or a measured false-alarm rate. A finite trace with no false alarms cannot establish a guarantee about all future behavior. [1]
Chandra and Toueg construct an eventually perfect detector using heartbeat messages and increasing timeouts under eventual bounds on relative process speeds and message transmission. The algorithm and those assumptions matter; increasing a timeout or selecting a phi threshold alone is not a proof that an implementation belongs to the class. [1]
Partial synchrony separates unknown bounds from bounds that hold after an unknown stabilization time. Neither formulation turns eventual accuracy into an operational completion deadline. [2]
Relations
Limitations
- These crash-stop process properties do not certify storage health, establish Byzantine fault tolerance, cover recovery after restart or enforce fencing against a stale writer. [1]
Citations
- Chandra and Toueg. Unreliable Failure Detectors for Reliable Distributed Systems. JACM 43(2), 225-267, 1996; sections 2.1-2.4 and 9.
- Dwork, Lynch and Stockmeyer. Consensus in the Presence of Partial Synchrony. JACM 35(2), 288-323, 1988; sections 1.2-1.3 and 2.3.
Sources & caveats
- CT1996 sections 2.1-2.4 and Figure 1 define diamond-P; section 9 and Theorem 9.1 give the partially synchronous implementation and assumptions.
- DLS1988 sections 1.2-1.3 and 2.3 distinguish timing models. The finite-trace qualification is an inference from the eventual, all-future-time property; no implementation was benchmarked.