Failure Detection: Deciding a Node Is Dead

TL;DR: Perfect failure detection is impossible in asynchronous networks. Every detector trades false positives (declaring live nodes dead, triggering unnecessary failovers) against false negatives (missing dead nodes, leaving clients hanging on zombies). Fixed-timeout heartbeats work for stable links. Phi-accrual detectors adapt to observed jitter (Cassandra convicts at phi threshold 8.0, roughly 18 seconds of silence)^[1]. SWIM gossip scales detection to thousands of nodes with O(1) bandwidth per member^[2]. In production, layer these: LB health checks for fast removal from the forward path, cluster-internal detection for membership consensus, and quorum-gated decisions to prevent single-observer false positives.

Learning Objectives#

After this module, you will be able to:

• Explain why perfect failure detection is impossible in asynchronous systems
• Design heartbeat intervals and timeouts for your network's p99 latency
• Describe phi-accrual: probabilistic suspicion that adapts to observed jitter
• Describe SWIM/Lifeguard gossip-based failure detection and its anti-entropy properties
• Distinguish LB health checks from cluster membership protocols
• Avoid flapping through hysteresis, grace periods, and quorum-gated decisions

Intuition#

You call a friend. The phone rings six times, then voicemail. Are they dead? Probably not. They might be in the shower, driving, or ignoring you. You try again in five minutes. Still no answer. Now you are more suspicious, but not certain. You text a mutual friend: "Have you heard from Alex today?" If three friends all say "no contact since yesterday," you start to worry.

This is failure detection. A single missed heartbeat tells you nothing. Repeated silence raises suspicion. Corroboration from independent observers raises it further. But you never reach certainty, because the friend might be on a plane with no signal, perfectly alive but unreachable. Every distributed system faces this exact dilemma: silence is ambiguous, and you must act anyway.

The rest of this chapter gives you the tools to act wisely: how to set timeouts, how to adapt them to observed conditions, how to corroborate suspicion across peers, and how to avoid the operational nightmare of flapping between "alive" and "dead" every few seconds.

Theory#

Why it is fundamentally hard#

In an asynchronous network, there is no upper bound on message delivery delay. A node that has not responded in 5 seconds could be crashed, GC-pausing, partitioned, or alive with its reply still in flight. No local observer can distinguish these cases from a single missed message^[3].

FLP (Fischer, Lynch, Paterson, 1985) sharpens this into an impossibility result: no deterministic protocol can guarantee consensus in an asynchronous system with even one crash failure, because the system cannot reliably tell a crashed process from a slow one^[4].

Chandra and Toueg's 1996 response defines failure detectors as oracles that output a set of suspected peers. They characterize detectors by two properties:

• Completeness: every crashed process is eventually suspected.
• Accuracy: correct processes are not wrongly suspected (to varying degrees).

They prove that the weakest detector sufficient to solve consensus is "eventually weak" (diamond-W, equivalent to Omega), which guarantees that eventually some correct process is never suspected by any correct process^[5]. The practical takeaway: every production failure detector is a probability judgment. The system around it must tolerate both false positives and false negatives.

Heartbeats and timeouts#

The simplest detector: peer A sends a heartbeat to monitor M every I milliseconds. M declares A dead if no heartbeat arrives within K * I milliseconds.

Choosing the timeout:

• Start with your network's p99 RTT plus expected processing jitter.
• Add a safety margin (typically 2-4x the heartbeat interval).
• etcd uses a 100 ms heartbeat interval and a 1,000 ms election timeout (10x the heartbeat), and recommends at least 10x to absorb jitter^[6].
• Kubernetes kubelets update a Lease object every 10 seconds; the node controller declares a node Unknown after 40 seconds of silence (4x the update frequency)^[7].

The problem: static timeouts do not adapt. A timeout tuned for normal conditions is too aggressive during a brief latency spike (false positive) and too conservative the rest of the time (slow detection). Linux TCP keepalive defaults to 7,200 seconds (2 hours) before the first probe^[8], which is useless for cluster detection.

Simple heartbeat detection: the monitor marks a peer dead after K consecutive missed heartbeats, but cannot distinguish a crash from a GC pause or network delay.

Phi-accrual detectors#

Introduced by Hayashibara, Defago, Yared, and Katayama at SRDS 2004, the phi-accrual detector outputs a continuous suspicion level instead of a binary alive/dead^[9]. Applications choose a phi threshold for their tolerance.

How it works:

1. Record the last N inter-arrival times of heartbeats (Cassandra uses N = 1,000)^[10].
2. Compute the mean inter-arrival time from the sample window.
3. On query, compute phi = (time since last heartbeat) / mean interval.
4. Scale by PHI_FACTOR (1 / ln(10) = 0.434) and compare against the threshold.

Cassandra's default phi_convict_threshold is 8.0^[1:1]. With a 1-second gossip interval, a node must be silent for roughly 8 / 0.434 = 18.4 seconds before conviction^[1:2]. In cloud or cross-DC environments, operators raise the threshold to 10-12 to absorb higher jitter.

The key advantage: the same phi = 8 threshold means stricter detection on a stable link (where mean inter-arrival is tight) and more tolerant detection on a jittery link (where mean inter-arrival is wide). The detector self-tunes per peer.

The GC-pause guard: Cassandra's MAX_LOCAL_PAUSE_IN_MS (default 5,000 ms) prevents a stop-the-world pause on this node from falsely convicting all peers when scheduling resumes^[10:1]. Without it, a 10-second GC pause would cause every peer's phi to spike simultaneously.

Cassandra's phi-accrual detector normalizes elapsed silence by observed mean interval; the MAX_LOCAL_PAUSE guard prevents self-inflicted mass convictions after a GC pause.

Gossip: SWIM and Lifeguard#

SWIM (Scalable Weakly-consistent Infection-style Process Group Membership) was introduced by Das, Gupta, and Motivala at DSN 2002^[2:1]. Each node, once per protocol period T:

1. Picks a random peer and sends a ping.
2. If no ack within a sub-timeout, picks K random helpers and asks them to ping-req the target (indirect probe).
3. If both direct and indirect probes fail, marks the target suspect and gossips that state.

Membership updates piggyback on pings and acks, so steady-state bandwidth per node is O(1) in group size. Detection time is independent of cluster size^[2:2].

Lifeguard extensions (Dadgar, Phillips, Currey, HashiCorp 2017)^[11] add three mechanisms:

• Self-awareness: Each node tracks a "nack" counter. Missing nacks from helpers imply the local node itself is struggling, so it dampens its own accusations. A tired observer should not accuse others.
• Dogpile resistance: The suspicion timeout starts long and shrinks as independent confirmations arrive. Fast failures resolve quickly; single-observer accusations time out.
• Buddy system: A suspect node that hears the gossip can immediately broadcast a refutation with a higher incarnation number.

Consul and Serf deploy SWIM + Lifeguard with a 1-second LAN probe interval and roughly 10 seconds from suspicion to dead at defaults^[12]. Lifeguard requires zero operator configuration; it self-tunes based on observed nack rates.

SWIM's indirect probe filters single-observer false positives: if K helpers can reach the target, the problem is the prober's link, not the target's health.

LB health checks vs cluster membership#

These solve different problems with different timing:

LB health checks optimize for fast removal of a bad target from the forward path. AWS ALB defaults: 30-second interval, 5-second timeout, 2 consecutive failures to mark unhealthy, 5 consecutive successes to return^[13]. They are binary (healthy/unhealthy) and unilateral (the LB decides alone).

Cluster membership protocols (Cassandra gossip, Consul SWIM, Redis Cluster bus) optimize for a correct, cluster-wide consensus view. They run on their own intervals, require corroboration, and tolerate slower detection because false positives are expensive (triggering rebalances, replica elections, hinted-handoff storms).

Passive outlier detection (Envoy) catches what active probes miss: a node that passes /health but returns 500s on real traffic. Envoy tracks per-upstream success rates and ejects hosts that deviate from the cluster mean by more than a configured standard deviation factor^[14].

Flapping mitigation#

Flapping is rapid toggling between alive and dead. Each toggle costs a failover, a client reconnect, or a rebalance. Mitigation strategies:

Hysteresis: Different thresholds for going down versus coming back up. ALB uses 2 failures to mark unhealthy but 5 successes to return^[13:1]. This asymmetry is intentional.

Grace periods: Kubernetes initialDelaySeconds on probes; Cassandra's MAX_LOCAL_PAUSE guard after a stop-the-world pause^[10:2]. The Kubernetes node controller uses a 40-second grace period before transitioning a node to Unknown^[7:1].

Rate limits on state transitions: Kubernetes evicts pods at 0.1 nodes/second (one node per 10 seconds) and slows further when a zone-wide failure is suspected (>55% of nodes in a zone unhealthy)^[15].

Quorum-gated decisions: Redis Cluster requires majority-masters agreement before escalating a local PFAIL to a cluster-wide FAIL. A node marks a peer PFAIL after no reply within cluster-node-timeout (15 seconds default). Escalation to FAIL requires that a majority of masters independently report PFAIL within 2 * NODE_TIMEOUT (30 seconds)^[16]. Only FAIL triggers a replica election.

Redis Cluster's two-phase detection: PFAIL is a local suspicion; FAIL requires majority-masters corroboration, eliminating single-observer false positives at the cost of up to 30 seconds of detection latency.

Real-World Example#

Cassandra phi-accrual on a 200+ node cluster#

Consider a 200-node Cassandra cluster running JVM workloads with periodic 2-second stop-the-world GC pauses. Without safeguards, here is what happens:

1. Node A pauses for 2 seconds during a G1 mixed collection.
2. On resume, A's failure detector checks every peer. Time since last heartbeat for all peers is now 2+ seconds. With a 1-second mean inter-arrival, phi = 2.0 / 1.0 = 2.0, scaled to 2.0 * 0.434 = 0.87. This is below threshold 8, so a 2-second pause alone does not convict.
3. But if A paused for 10 seconds (a pathological full GC), phi would be 10.0 * 0.434 = 4.34 per peer. Still below 8. However, if the pause coincides with a peer that was already 8 seconds late, the combined elapsed time pushes phi over threshold, and A wrongly convicts that peer.
4. Worse: if A itself stops sending heartbeats during the pause, other nodes see A as silent for 10 seconds. With mean = 1 second, phi = 10 * 0.434 = 4.34 on each observer. Not enough for conviction at threshold 8, but a second missed cycle pushes it over.

Cassandra's layered defense:

• MAX_LOCAL_PAUSE guard: If the detector's own interpret() loop detects a gap longer than 5,000 ms since its last run, it logs a warning and refuses to convict anyone^[10:3]. This is the primary defense against self-inflicted mass convictions.
• Initial interval seeded high: The arrival window seeds at 2 * gossip interval (2,000 ms), erring conservative because false positives trigger hinted-handoff storms that are worse than slow detection^[10:4].
• Tunable threshold: Operators in cloud environments raise phi_convict_threshold from 8 to 10-12, buying more tolerance for jitter at the cost of slower detection^[1:3].
• GC tuning: The real fix is bounding pause times. G1 with -XX:MaxGCPauseMillis=200 or Shenandoah/ZGC for sub-millisecond pauses eliminates the root cause.

The operational lesson: phi-accrual adapts to network jitter beautifully, but it cannot adapt to local scheduling pauses that affect the detector itself. You need a separate guard for that.

Trade-offs#

Cluster-internal detection#

Layered controls (run alongside cluster detection)#

Common Pitfalls#

Exercise#

Your 200-node Cassandra cluster experiences routine 2-second GC pauses on individual nodes, which currently causes the phi detector to flag them dead and trigger hinted-handoff storms. Design a fix: tune phi, add grace periods, change GC strategy, or switch detection approach. Decide what you would actually change first.

Key Takeaways#

• Perfect failure detection is impossible in asynchronous networks. Every detector chooses between false positives and false negatives.
• Start with heartbeats plus a timeout tuned to 3-4x your observed p99 latency under load. Add phi-accrual or SWIM when scale or variability demands it.
• Phi-accrual adapts to per-peer jitter automatically, but cannot protect against local scheduling pauses. Use a separate pause guard.
• SWIM scales detection to thousands of nodes with O(1) bandwidth per member. Lifeguard's self-awareness prevents degraded observers from falsely accusing peers.
• LB health checks and cluster failure detection serve different purposes with different timing. Do not conflate them.
• Quorum-gated decisions (Redis PFAIL-to-FAIL, Sentinel SDOWN-to-ODOWN) eliminate single-observer false positives at the cost of detection latency.
• Zombie nodes (slow but alive) are often worse than dead nodes. Invest in passive outlier detection, not just binary alive/dead checks.

Further Reading#

• Unreliable Failure Detectors for Reliable Distributed Systems - Chandra and Toueg's 1996 paper defining the failure detector hierarchy; won the 2010 Dijkstra Prize and remains the formal foundation for all production detectors.
• The Phi Accrual Failure Detector - Hayashibara et al., SRDS 2004; the original paper behind Cassandra and Akka's adaptive detection.
• SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol - Das, Gupta, Motivala, DSN 2002; the gossip protocol that Consul, Serf, and Nomad implement.
• Lifeguard: Local Health Awareness for More Accurate Failure Detection - Dadgar, Phillips, Currey (HashiCorp) 2017; the three extensions that make SWIM production-safe under CPU exhaustion.
• AWS Builders Library: Implementing health checks - Yanacek's operational playbook for shallow vs deep checks, fail-open behavior, and the liveness/dependency split.
• Redis Cluster specification - The canonical reference for PFAIL/FAIL state machine, gossip protocol, and replica election timing.
• Impossibility of Distributed Consensus with One Faulty Process - Fischer, Lynch, Paterson, JACM 1985; the FLP result that proves why failure detection cannot be perfect.
• etcd Tuning Guide - Practical guidance on heartbeat/election timeout ratios for Raft-based consensus under varying network conditions.

Flashcards#

References#