Failure models and failure detectors.

Article 1.1 named the failure spectrum informally — crash, omission, timing, Byzantine. This article makes "is that node down?" formally precise, because every consensus algorithm in this series has to answer that exact question constantly, and answering it wrong in either direction (declaring a live node dead, or a dead node live) breaks correctness or availability. Chandra & Toueg's 1996 "unreliable failure detectors" paper is the foundational treatment: it names exactly two properties a detector can offer — completeness and accuracy — proves you can't have both perfectly in an asynchronous network, and classifies eight useful detector strengths along that trade-off. This is the formal scaffolding that timeouts, heartbeats, and every leader-election protocol in Phase 4 onward are quietly built on top of.

Why "just check if it responds" needs a formal treatment at all

The naive approach to failure detection sounds trivial: ping a node, if it doesn't respond within some timeout, mark it dead. Article 1.1 already flagged the core problem with this — you cannot distinguish "the node crashed" from "the node (or the network between you) is just slow," because in an asynchronous network (article 1.1's "Lie #1," no bound on message delay), any timeout you pick could, in principle, be too short for a message that's simply taking longer than usual. This isn't a tuning problem you solve by picking a bigger number — no finite timeout can be proven correct in a truly asynchronous system, because there's always some slower-but-still-alive scenario your timeout would misclassify.

Chandra and Toueg's contribution was to stop trying to build a perfect detector (provably impossible, as you'll see) and instead formally characterize which imperfections a detector can offer, precisely enough that you can reason about which imperfections a given consensus algorithm can tolerate and still remain correct.

The two properties: completeness and accuracy

Every failure detector is evaluated along two independent axes:

• Completeness — does the detector eventually suspect every node that actually crashes? A detector with strong completeness guarantees every crashed process is eventually permanently suspected by every correct process. Weak completeness only guarantees every crashed process is eventually suspected by some correct process — a much weaker, less useful guarantee on its own.
• Accuracy — does the detector avoid falsely suspecting nodes that are actually alive? Strong accuracy means no correct process is ever suspected by anyone, ever. Weak accuracy means at least one correct process is never suspected by anyone. Eventual variants of both (eventually strong, eventually weak) relax this to "after some unknown point in time" rather than "always from the start" — a crucial, practical relaxation, because it accepts that a detector might be temporarily wrong (suspect a slow-but-alive node) as long as it eventually stabilizes and stops.

The eight detector classes

Combining the two completeness levels (strong, weak) with the four accuracy levels (strong, weak, eventually strong, eventually weak) gives eight named classes, denoted with letters — P (perfect), S (strong), ◇P (eventually perfect), ◇S (eventually strong), and weaker variants of each. The two that matter most in practice, and that you'll see referenced again when Paxos and Raft are introduced in Phase 5, are:

How real systems implement this: heartbeats and timeouts

The formal ◇S-class guarantee is achieved in practice by mechanisms far simpler than the theory might suggest — this is a recurring, comforting pattern in distributed systems: elegant impossibility results are often circumvented by unglamorous engineering that happens to satisfy exactly the weaker guarantee that's actually sufficient.

class SimpleFailureDetector:
    def __init__(self, timeout_ms=150):
        self.timeout_ms = timeout_ms
        self.last_heartbeat = {}   # peer_id -> last_seen_timestamp
        self.suspected = set()

    def on_heartbeat_received(self, peer_id, now):
        self.last_heartbeat[peer_id] = now
        self.suspected.discard(peer_id)   # un-suspect on any sign of life

    def check_timeouts(self, now):
        for peer_id, last_seen in self.last_heartbeat.items():
            if now - last_seen > self.timeout_ms:
                self.suspected.add(peer_id)   # suspect, NOT "confirmed dead"
                # a heartbeat arriving late will un-suspect via on_heartbeat_received
                # this "suspect, then un-suspect on recovery" pattern is what
                # gives eventual accuracy despite occasional false positives

Two details in that sketch matter more than they look: (1) a "suspected" node is never marked permanently, irrevocably dead by this mechanism alone — the moment a heartbeat arrives, suspicion is lifted, which is precisely the "eventually" in eventually-accurate. (2) the timeout value is a tuning knob with a genuine trade-off, not a correctness parameter: too short, and you get frequent false suspicions (a node under a GC pause gets marked suspect, then un-suspects a moment later — wasted leader-election churn, covered in article 4.2); too long, and real crashes take longer to detect and react to. There is no value that's "correct" in an absolute sense — only a value tuned to your network's actual latency distribution and your tolerance for false positives versus detection speed.

The modern practical answer: phi-accrual failure detectors

A fixed timeout is a blunt instrument — it treats "150ms of silence on a network that's usually silent for 20ms" identically to "150ms of silence on a network that's usually silent for 140ms," even though the first is a much stronger signal of trouble than the second. The phi-accrual failure detector (Hayashibara et al., 2004) is the widely-adopted practical refinement, used in Cassandra and Akka among others: instead of a binary suspect/not-suspect flag, it outputs a continuous suspicion level (phi, φ) computed from the statistical distribution of recently observed heartbeat intervals.

Concretely: the detector tracks the historical distribution of inter-arrival times between heartbeats from a given peer, and computes, at any moment, how statistically unlikely the current silence duration is given that history — a peer whose heartbeats normally arrive every 100ms ± 10ms triggers rapidly rising suspicion after 200ms of silence, while a peer with historically noisy, irregular 50-500ms intervals is granted more patience before the same suspicion level is reached. This lets applications set a suspicion threshold appropriate to their tolerance for false positives versus detection latency, rather than guessing a single fixed millisecond value that has to somehow be right for every peer's actual network behavior.

One more distinction worth being precise about: detecting failure vs. detecting partition

A failure detector, as formalized here, cannot distinguish "the peer crashed" from "we're partitioned from the peer" — and by design, it doesn't try to. Both produce identical observable behavior (silence past the timeout), which is exactly the ambiguity article 1.1 named as fundamental. What a failure detector does give you is a consistent, systematic way to act despite that ambiguity — suspect, and let the rest of the system (the consensus algorithm's majority-quorum logic, from article 1.2) handle the consequences safely regardless of which underlying cause is true. This is exactly why majority quorums matter so much: they make the system's behavior correct even when the failure detector's suspicion is wrong (a "crash" that was really just a slow node), because the majority mechanism, not the failure detector, is what's actually load-bearing for safety.

FAQ

Takeaways

• Every failure detector is characterized by two independent properties: completeness (does it eventually suspect every real crash?) and accuracy (does it avoid falsely suspecting live nodes?).
• Perfect completeness and perfect accuracy together are unachievable in an asynchronous network — the same underlying ambiguity as article 1.1's "Lie #1."
• Chandra & Toueg (1996) classify eight useful detector strengths; the class ◇S (eventually strong) is the headline result — the weakest detector class proven sufficient to make consensus solvable despite crash failures.
• Real systems implement this with heartbeats and timeouts — suspicion that's lifted the moment a heartbeat arrives, giving practical "eventual accuracy" without any formal detector machinery.
• Phi-accrual failure detectors (Cassandra, Akka) replace a fixed timeout with a continuous, per-peer-adaptive suspicion level derived from historical heartbeat-interval statistics — the practical modern standard.
• A failure detector cannot and does not try to distinguish "crashed" from "partitioned" — it exists to let the system act consistently despite that ambiguity, with majority quorums (article 1.2) providing the actual safety guarantee even when suspicion is wrong.
• This article is the direct bridge to FLP (next): Chandra-Toueg shows exactly how much "extra help" (a ◇S-class detector) is needed to get around the impossibility FLP proves for a fully leaderless, detector-free asynchronous system.

References & further reading

• Chandra & Toueg — Unreliable Failure Detectors for Reliable Distributed Systems (1996) — the primary source; completeness/accuracy formalization and the eight detector classes.
• Hayashibara et al. — The φ Accrual Failure Detector (2004) — the practical, widely-deployed refinement used in Cassandra and Akka.
• cvam.sight — Consensus 1.1: Why Distributed Systems Are Hard — the informal failure spectrum this article formalizes.