SWIM, Gossip, and Phi-Accrual: How Clusters Know Who's Alive

Every distributed system contains a quiet embarrassment: it cannot actually tell whether a machine is dead. A silent node might be crashed, GC-paused, partitioned, or just slow — and no amount of waiting distinguishes them (that impossibility is the FLP result's street form). Yet every membership decision — reroute traffic, promote a replica, rebalance shards — hangs on exactly this undecidable question. Failure detection is the load-bearing guess under everything else, and its design space — heartbeats, SWIM, phi-accrual — shows up verbatim inside Cassandra, Consul, Serf, Akka, and every service mesh.

Why all-to-all heartbeats die first

The naive scheme — everyone pings everyone every second — costs O(N²) messages per period: at 1,000 nodes, a million pings/sec of pure overhead, and each node maintaining timeout state for 999 peers. Centralizing it (everyone heartbeats a monitor) restores O(N) but builds a single point whose own failure is indistinguishable from everyone's, plus a blast-radius problem when it flaps. The scaling law you want: per-node load constant in cluster size, detection time growing at most logarithmically.

SWIM: constant load, probabilistic completeness

SWIM's protocol period, per node, regardless of cluster size:

every T (say 1s), node A:
  1. pick ONE random member B; ping it
  2. no ack within timeout? ask k others (say 3): "ping B for me"
     -> indirect probes: any of them reach B, A gets an ack relayed
  3. still nothing? mark B SUSPECT (not dead) and gossip that
  4. suspect survives a timeout without refutation -> CONFIRMED dead

Each ingredient kills a specific false-positive class. Random probing spreads detection duty with no coordination — every member gets probed in expectation each period across the cluster. Indirect probes (step 2) are the subtle one: they distinguish "B is down" from "the A↔B path is down" — a partial network partition stops being a death sentence pronounced by whoever happens to sit behind the bad link. Suspicion (step 3) inserts a refutation window: B, seeing itself gossiped as suspect, broadcasts an incarnation-numbered "I'm alive" that overrides the suspicion. GC pauses and CPU stalls get to un-condemn themselves.

Membership updates travel by piggybacked gossip — no extra messages; updates ride along on pings and acks, reaching everyone in O(log N) periods with high probability. Incarnation numbers (bumped only by the accused node refuting its own suspicion) give updates a total order per member, so a stale "alive" can never resurrect a confirmed death — the same monotonic-epoch trick as fencing tokens, applied to identity.

Phi-accrual: suspicion as a float, not a bit

The orthogonal refinement (Cassandra's detector): binary timeouts encode one arbitrary threshold, but inter-arrival times of heartbeats have a distribution. Phi-accrual keeps a sliding window of recent inter-arrival times and outputs a continuous suspicion level — φ = -log₁₀(P(silence this long | history)) — so φ=1 means "10% chance this silence is normal," φ=8 means one-in-10⁸.

The two design consequences: thresholds become per-link and adaptive (a node across a jittery WAN link earns a wider tolerance than a rack neighbor, automatically), and different consumers apply different thresholds to the same signal — routing might dodge a node at φ=3 while replica promotion waits for φ=10. Detection stops being a global verdict and becomes a risk dial each subsystem reads at its own tolerance. That split — cheap evidence collection, per-consumer decision — is the transferable pattern.

Lifeguard: the slow node problem

HashiCorp's production scars (Serf/Consul) produced Lifeguard, whose insight inverts the frame: many "failure detections" are caused by the detector being sick, not the target. An overloaded node times out everyone it probes and floods the cluster with false accusations. Lifeguard's fixes: a node that isn't receiving expected acks about itself widens its own probe timeouts (self-awareness: "maybe I'm the problem"); suspicion timeouts scale with how many independent accusers exist (one accuser = long fuse, five = short). False positives drop ~50× with negligible extra cost. The meta-lesson generalizes to any monitoring you build: an unhealthy observer is indistinguishable from an unhealthy observed — good detectors model their own degradation.

Where the guess becomes truth

Gossip-based membership is eventually agreed, probabilistically fast — perfect for routing tables, load balancing, hinted-handoff targets. It is not a basis for safety-critical exclusivity: "the cluster thinks node X is dead" must never by itself authorize taking X's locks or splitting its shard, because X may disagree and still be writing. Safety comes from pairing the detector with leases and fencing tokens (X's authority expires on a clock X itself respects; storage rejects stale-epoch writers) or from running membership through consensus (Raft-managed member lists) where changes are rare and correctness-critical. The layering to say out loud: gossip detection for liveness reactions, epochs/leases for safety; systems that let the first drive the second directly have a split-brain story waiting to run.

Interview probe	Answer sketch
Detection time vs false positives?	The fundamental dial — shorter timeouts detect faster and accuse wrongly more; phi-accrual makes the dial explicit and adaptive
Node flapping up/down?	Incarnation numbers order the gossip; add hysteresis (rejoin cooldown) so flappers don't churn shard placement
10K nodes?	SWIM load is constant per node; gossip convergence O(log N) — the thing that breaks first is humans reading membership churn, so batch/dampen updates
Why did Consul/Cassandra pick these?	Because they're leaderless: membership must work before and during any election — the detector can't depend on what it enables

The distilled hierarchy: random probing for constant load, indirect probes for path-vs-node discrimination, suspicion windows for refutation, continuous suspicion for adaptive thresholds, self-awareness for sick observers, and epochs so the whole probabilistic apparatus never gets to overrule safety. Each layer exists because the previous one, alone, condemned an innocent machine.