Commentary: failure-detector

Two ways to decide a node is dead, over the same heartbeats: a constant timeout, and Hayashibara's phi-accrual detector, which fits a model of the network and convicts when the silence gets improbable. The adaptive one convicts a healthy node on the single heartbeat where the network changes, and then goes on to tolerate a longer silence than the one it just killed for. A study guide for detector.py.

cd failure-detector
python3 demo.py           # the aha (§6), about 20 seconds
python3 test_detector.py  # pins every number this page claims

1. Orientation

This toy is a failure detector: the component that turns "I haven't heard from that node lately" into "that node is dead," which is the input every leader election, every failover, and every membership protocol is built on top of.

It ships two of them over the identical heartbeat stream:

• FixedDetector(timeout_ms) — suspects after a constant silence.
• PhiDetector(threshold) — fits a normal distribution to the inter-arrival times it has seen and suspects when the current silence is improbable under that fit. This is the detector in Akka and Cassandra.

The shortest version of the result:

from detector import PhiDetector, heartbeat_trace

arrivals, _ = heartbeat_trace(4, [(40, 10.0, 3.0), (30, 80.0, 40.0), (30, 10.0, 3.0)])
d = PhiDetector()                    # threshold 8, the shipped default
d.heartbeat(arrivals[0])
for i in range(1, len(arrivals)):
    if d.suspects(arrivals[i]):      # the node is alive; it just sent this
        print(f"convicted at beat {i} on a "
              f"{arrivals[i] - arrivals[i-1]:.1f} ms gap")
    d.heartbeat(arrivals[i])

By the end you should be able to say why an adaptive detector is at its worst precisely when the thing it adapts to changes, why the fix that production ships is a hard-coded constant, and why "just tune the timeout" is a better answer than its reputation suggests.

2. The problem this mechanism exists to solve

A failure detector has exactly one kind of evidence — heartbeats that stopped arriving — and it is being asked a question that evidence cannot answer. A dead node and a slow network are indistinguishable from the outside. In an asynchronous network there is no silence long enough to be proof, because there is no bound on message delay to compare it against.

So every detector is choosing a point on a trade-off, and the two ends are both real costs:

• Convict too fast and you get false positives: a healthy node is evicted, its shards are rebalanced, its leases are revoked, and the cluster does a great deal of expensive work to recover from something that never happened. Worse, the eviction itself generates load, which makes the network slower, which produces more false positives.
• Convict too slow and every real crash costs you that much extra unavailability, during which requests route to a node that is not there.

The phi detector's pitch is that this trade-off shouldn't be resolved by a constant chosen at deploy time by someone guessing at the network. Instead it should be learned: watch the inter-arrival times, and let the threshold follow the network's actual behaviour. On a calm network, be aggressive. On a congested one, be patient. One knob (threshold), expressed in units that mean something — a probability — rather than milliseconds that mean nothing without knowing the network.

That pitch is good enough that it is the default in Akka and Cassandra. This toy is about what it costs.

3. Background you need

The two starred rows carry the result. Everything on this page follows from the fact that sigma is estimated from recent data and therefore describes the network you had, not the network you have.

4. The mental model

Both detectors watch the same thing — elapsed silence — and differ only in what they compare it against.

That is the whole toy. The same detector, four heartbeats apart, convicts a 132.6 ms silence and acquits a 142.8 ms one — because between the two, the window learned that the network had got noisier, and sigma grew from 3.58 to 9.04. The bell curve got wider, so the same distance from the mean stopped being remarkable.

Adaptivity means the verdict depends on the history, not just the evidence.

5. Reading the source

The fixed detector is the whole of the baseline, and it is four lines:

    def __init__(self, timeout_ms: float):
        self.timeout_ms = timeout_ms
        self.last_arrival = 0.0

    def heartbeat(self, arrival_ms: float) -> None:
        self.last_arrival = arrival_ms

    def suspects(self, now_ms: float) -> bool:
        return now_ms - self.last_arrival > self.timeout_ms

detector.py · lines 37–45

It has no memory beyond the last arrival and no model at all. That is worth holding onto, because it is exactly why it cannot be surprised: there is no belief about the network for the network to violate.

Now phi. This is the method the entire page is about:

    def phi(self, now_ms: float) -> float:
        if self.last_arrival is None:
            return 0.0
        elapsed = now_ms - self.last_arrival
        mu = statistics.fmean(self.intervals)
        sigma = max(statistics.pstdev(self.intervals), self.min_stddev_ms)
        # P(X > elapsed) for X ~ Normal(mu, sigma), via the complementary
        # error function. Clamped because the tail underflows to 0.0 long
        # before the silence gets interesting.
        p_later = 0.5 * math.erfc((elapsed - mu) / (sigma * math.sqrt(2.0)))
        return -math.log10(max(p_later, 1e-300))

detector.py · lines 89–99

Read the middle two lines as a pair. mu and sigma are re-fitted on every call from the last 100 intervals. The detector does not have a threshold; it has a procedure for computing one, and the procedure's inputs are the recent past.

max(..., self.min_stddev_ms) is the load-bearing line in this file. It looks like defensive programming — avoid dividing by zero when every interval is identical — and it is also the only thing standing between the detector and the failure mode in §6. §6.3 turns it into the difference between 384 false alarms and 5.

The 1e-300 clamp is a smaller decision with a consequence worth knowing: phi saturates at 300. Once a silence is that improbable, phi stops distinguishing 200 ms from four seconds. That never changes a convict/acquit decision at threshold 8, but it does mean phi is not a distance — you cannot subtract two phis and get anything meaningful. test_detector.py::phi_saturates_at_300_because_the_normal_tail_underflows pins it.

One detail in heartbeat that is easy to get wrong:

    def heartbeat(self, arrival_ms: float) -> None:
        # The first heartbeat establishes a reference point and nothing else:
        # there is no *interval* until two have arrived. Recording one here
        # would put the node's join time into the window as if it were a
        # network delay.
        if self.last_arrival is not None:
            self.intervals.append(arrival_ms - self.last_arrival)
        self.last_arrival = arrival_ms

detector.py · lines 80–87

Without the guard, a node joining at wall-clock 09:41:23 contributes an "interval" of about 35 billion milliseconds to the window, and the detector spends the next 100 heartbeats believing the network is unimaginably slow. This is the sort of bug that only shows up in production, on restart.

6. The demo, and what it proves

The scenario: a sender emits a heartbeat every 100 ms and never varies. Only the network delay changes — calm N(10, 3) ms for 40 beats, congested N(80, 40) ms for 30, then calm again for 30. After beat 100 the sender dies. 200 seeded traces.

6.1 The moment the network changes

Beat 40 is the first congested heartbeat, and the node is alive — it just sent the packet being measured. Derive the verdict:

(That reproduces the table's 19.48 to within the rounding the table itself does — the demo computes phi from unrounded mu and sigma, which are 99.9174 and 3.5816.)

Threshold 8 means "convict when this silence is a 1-in-10^8 event." A 132.6 ms gap qualifies, because the model was fitted to a network whose gaps had a standard deviation of 3.58 ms. Under that network, it is.

Now beat 44, four beats later, on a longer gap:

The gap grew by 10.2 ms and the verdict flipped from guilty to innocent, because sigma grew 2.5× in the meantime. The detector needed to be wrong once in order to learn.

6.2 It is not a fluke of one seed

Every one of the 200 traces produces at least one false conviction, and in four out of five the detector goes on to shrug at a silence 40 ms longer than the one it convicted on. 173 of the 200 fire on beat 40 specifically — 45% of all 384 false alarms land on the single heartbeat where the regime changes.

And the tuning does not rescue it:

A fixed 250 ms timeout raises 20 false alarms and detects in 159.8 ms. Phi at its standard threshold of 8 raises 384 and detects in 179.7 ms — worse on both axes at once, which is what "dominated" means in that column. Raising the threshold trades false alarms for latency along phi's own curve and never gets it back onto the frontier; test_detector.py::raising_the_threshold_never_lets_phi_escape_domination pins that for thresholds 8 through 20.

6.3 The load-bearing line

One constant, changed from 1 ms to 30 ms, takes 384 false alarms to 5 — and costs 8 ms of detection latency to do it. At 50 ms it reaches zero, and now costs 110 ms.

Read that table twice. The adaptive detector is rescued by hard-coding a floor that tells it to distrust its own variance estimate. The fix for "too adaptive" is "be less adaptive," and the knob is measured in milliseconds — the same unit the phi detector was supposed to free you from.

6.4 It is not about the change being sudden

The obvious explanation is that a step change is unfair, and a real network would degrade gradually. It doesn't help:

Ramping the congestion in over 30 heartbeats still leaves 322 false alarms, and short ramps are worse than the step. A gradual ramp keeps the mean creeping upward while the 100-sample window stays dominated by calm data, so sigma stays small for longer. Smearing the change out gives the detector more opportunities to be surprised, not fewer.

6.5 The boundary: where the effect vanishes

It doesn't vanish, and that is worth being honest about. Removing the regime change entirely still leaves phi convicting live nodes (this table comes from cf_detector.py CF4, not from demo.py):

A regime change roughly doubles the damage and concentrates it at one instant, but a stationary network still produces false alarms, because a normal model of a right-skewed delay distribution underestimates its own tail. The effect this page is about — convicting at the transition — is what the change adds; the baseline is phi's model being wrong about the shape.

The place the comparison genuinely reverses is not in this toy. What does narrow with a stationary network is the margin: on all-congested traffic phi takes 374.6 ms to detect against fixed-300's 278.9 ms, so phi is still slower and still less accurate, but the fixed timeout there is a number someone had to know in advance. That is the honest case for phi: not that it wins on these axes, but that it gets to a defensible operating point without anyone having measured the network first. This toy's scenario is one where somebody did measure it.

7. Design decisions and roads not taken

Arrival times computed up front, never slept. heartbeat_trace returns a list of floats and every detector is a pure function of (history, now). The demo runs 200 traces in about 20 seconds instead of 20 seconds per trace, the output is byte-identical every run, and — the part that actually matters — §6.1's table can ask what the detector believed at one exact instant. A threads-and-time.monotonic() version of this toy could not have produced that table at all.

Suspicion is sampled at the next arrival, not on a polling grid. Both detectors are monotonic in elapsed time: silence never becomes less alarming while it continues. So the most alarming instant in any gap is the moment just before the next heartbeat lands, and checking exactly there is exact rather than a sample. The same monotonicity is what makes time_to_suspect's bisection valid, and it's stated in that function's docstring for the reader who wonders why a binary search is allowed.

The normal distribution, not the exponential. Hayashibara's paper fits a normal, and so does Akka; Cassandra's implementation does not. Fitting a distribution with the wrong shape is part of why §6.5's stationary traces still produce false alarms. A version of this toy that fitted an exponential would be a different, also-interesting toy — this one is about what happens when sigma moves, which is a property of any fitted scale parameter.

Detection latency measured from when the heartbeat was due, not from the last one that arrived. A detector should not be credited for network delay it already absorbed; measuring from the last arrival would flatter whichever detector happened to get a fast final packet.

No suspicion levels, no unreachable state, no gossip. Real membership systems don't act on one node's opinion — they disseminate suspicion and require corroboration, which is precisely a defence against the failure mode on this page. That's SWIM's design, and it is out of scope here for the same reason the toy has one node watching one other node: adding a quorum would make the false alarms mostly disappear and hide the mechanism that causes them.

8. What's simplified vs. the real thing

• One watcher, one watched. Real clusters have every node watching several others, and act on aggregated suspicion. Akka's cluster requires the failure detector's verdict plus gossip convergence before a node is marked unreachable; SWIM sends indirect probes through k other members before convicting. Both exist because a single detector's opinion is known to be this unreliable.
• The floor exists in production, and its documentation says why. Akka's reference configuration ships min-std-deviation = 100 ms — a hundred times this toy's default — with the comment: "Minimum standard deviation to use for the normal distribution in AccrualFailureDetector. Too low standard deviation might result in too much sensitivity for sudden, but normal, deviations in heartbeat inter arrival times." That is §6.3, written by the people who ship it.
• And so does the second constant. Akka also adds acceptable-heartbeat-pause = 3 s (10 s across data centres) on top of the fitted mean, described as a margin to "survive sudden, occasional, pauses in heartbeat arrivals, due to for example garbage collect or network drop." Between the floor and the pause, the shipped detector's behaviour on a calm network is dominated by two hard-coded milliseconds constants — which is the thing phi was pitched as replacing.
• The threshold gets tuned in practice, whatever the docs say. Cassandra's cassandra.yaml carries phi_convict_threshold: 8 with the comment "most users should never need to adjust this"; Akka's documentation recommends 12 on EC2. §6.2's table is what that recommendation looks like from the inside — moving along phi's curve, not off it.
• Delay is Gaussian and never reorders. Real network delay is right-skewed with a long tail, and packets do arrive out of order. heartbeat_trace forces arrivals monotonic; a detector that saw beat 7 after beat 8 would be answering a different question.
• Nothing is measured in wall-clock time, so this toy says nothing about the cost of running either detector. Phi does fmean and pstdev over 100 samples per call, which is not free at cluster scale; real implementations keep running sums instead.
• The sender's clock is perfect. Heartbeats leave at exactly 100 ms intervals. Real senders are subject to the same GC pauses and scheduler delays as the receiver, and a pause on the sending side is indexed by neither detector as anything other than network delay.

9. Check yourself

Q1. At beat 40 the window's sigma is 3.58 ms. If the floor min_stddev_ms had been set to 30 ms, what would phi have been on that same 132.6 ms gap — and would the node have survived?

Q2. The demo reports that a fixed 300 ms timeout detects a real crash in 209.8 ms — less than its own timeout. How is that possible?

Q3. Both detectors are monotonic in now, which the source uses to justify bisection in time_to_suspect. Is PhiDetector monotonic in elapsed silence if the window is still changing?

Q4. You run this detector in a cluster where nodes are evicted on conviction, and eviction triggers a shard rebalance that saturates the network for a few seconds. What happens, and which number in §6 predicts it?

Q5. Someone proposes shrinking the window from 100 to 10, arguing the detector will adapt to the new regime faster. Does it reduce false alarms?

10. Further reading

• Hayashibara, Défago, Yared & Katayama, The φ Accrual Failure Detector (SRDS 2004) — the original. Note that the paper's contribution is the accrual idea — output a suspicion level instead of a boolean, and let each application pick its own threshold — which this toy collapses back to a boolean at one threshold. If you take one thing from the paper that isn't here, take that.
• Chandra & Toueg, Unreliable Failure Detectors for Reliable Distributed Systems — the theory underneath. Defines detectors by completeness and accuracy properties, and proves what consensus needs. The false alarms on this page are accuracy violations, and the paper's point is that you can build correct systems on top of a detector that commits them.
• Akka: Failure Detector — the production phi detector, with the threshold-vs-detection-time chart this toy's §6.2 is a census of, and the recommendation to raise the threshold to 12 on EC2.
• Akka configuration reference — search for min-std-deviation. The comment beside it is §6.3 in one sentence, and the default is 100 ms.
• Apache Cassandra cassandra.yaml — search for phi_convict_threshold: default 8, "most users should never need to adjust this."
• Das, Gupta & Motivala, SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol — the other answer to this page's problem: instead of a better model, ask k other members to probe before convicting. Suspicion becomes a cluster property rather than one node's opinion.