Catalog My learning Blog
Distributed Systems Explained: CAP, Clocks and Replication · Phase 4 · Lesson 20 · 4 min read

Failure Detection: Heartbeats and Phi Accrual

On this page
  1. The failure detection trade-off
  2. Heartbeats with a fixed timeout
  3. Phi-accrual: suspicion as a number
  4. Gossip and SWIM in large clusters
  5. Designing around imperfect detection
  6. Check yourself

The failure detection trade-off

A node stops responding. Is it dead, or slow (Day 1)? A failure detector must decide when to give up waiting:

  • Short timeout: fast failover, but slow-but-alive nodes get declared dead. That triggers needless failovers, data movement, and sometimes two active leaders.
  • Long timeout: fewer false alarms, but real failures take longer to handle, and users wait.

You can't have both perfectly; FLP (Day 14) says so. Good detectors make the trade-off adaptive.

Heartbeats with a fixed timeout

Each node sends a heartbeat every second; if none arrives for, say, 5 seconds, it's suspected dead. Simple, used everywhere (Raft's election timeout, Kubernetes node heartbeats). The weakness: a fixed timeout ignores how the network really behaves. On a quiet LAN, 5 seconds is very slow; during a busy period with garbage collection pauses, 5 seconds might cause false alarms.

Phi-accrual: suspicion as a number

The phi-accrual failure detector (Hayashibara and colleagues, 2004) learns the normal distribution of heartbeat intervals and outputs a continuous suspicion level φ instead of a yes/no answer. φ = −log10(probability that a heartbeat would arrive this late if the node were alive). φ = 1 means about a 10 percent chance it's still alive; φ = 3, about 0.1 percent; φ = 8, about one in a hundred million.

Python
# phi.py: a phi-accrual failure detector (normal approximation of heartbeat intervals)
import math, random, statistics

class PhiAccrual:
    def __init__(self, window=200):
        self.intervals, self.last, self.window = [], None, window

    def heartbeat(self, now):
        if self.last is not None:
            self.intervals = (self.intervals + [now - self.last])[-self.window:]
        self.last = now

    def phi(self, now):
        mean = statistics.mean(self.intervals)
        std = max(statistics.stdev(self.intervals), 0.1 * mean)   # avoid a zero spread
        elapsed = now - self.last
        p_later = 0.5 * math.erfc((elapsed - mean) / (std * math.sqrt(2)))   # P(next beat later than this)
        return -math.log10(max(p_later, 1e-300))

With heartbeats arriving about every second (±0.1 s):

Code
0.5 s since last heartbeat -> phi   0.00
1.0 s since last heartbeat -> phi   0.32
1.3 s since last heartbeat -> phi   2.99
1.5 s since last heartbeat -> phi   6.76
2.0 s since last heartbeat -> phi  23.69

The application chooses a threshold, for example 8, and the detector adapts: on a jittery network the learned spread is wider, so suspicion rises more slowly; on a steady one, it rises fast. Cassandra (phi_convict_threshold, default 8) and Akka use phi-accrual detectors. Real implementations fit the distribution more carefully, but the idea is the same.

Fixed timeouts mark a node dead after a set silence; phi-accrual turns silence into a rising suspicion score based on the node's normal heartbeat pattern.
Fixed timeouts mark a node dead after a set silence; phi-accrual turns silence into a rising suspicion score based on the node's normal heartbeat pattern.

Gossip and SWIM in large clusters

With thousands of nodes, everyone heartbeating everyone is too much traffic. Gossip protocols spread membership and liveness: each node periodically exchanges state with a few random peers, and information spreads epidemically, reaching all nodes in roughly logarithmic rounds. SWIM (used by HashiCorp's Serf, Consul and memberlist) adds indirect probing: if A can't reach B, it asks a few other nodes to ping B before suspecting it, which separates "B is dead" from "the link between A and B is bad". Suspicion periods let a falsely suspected node refute it.

Designing around imperfect detection

  • Assume the detector will be wrong sometimes and make it safe: fencing tokens (Day 18), majorities, idempotent retries.
  • Tune per environment: measure normal heartbeat jitter, garbage collection pauses and network latency before choosing timeouts.
  • Distinguish reachability from health: a process can answer heartbeats while its disk is full; add application-level health checks.
  • Add hysteresis: require several missed heartbeats, and several successes before readmitting, so nodes don't flap.

Check yourself

Shorter timeouts detect real failures faster but produce more false suspicions of slow nodes; longer timeouts do the opposite.

It learns the spread of heartbeat intervals; with more variation, the same silence produces lower suspicion, so it waits longer before declaring failure.

A failed node from a broken link between two particular nodes. When a direct ping goes unanswered, the node asks a few other members to ping the suspect; if any of them succeed, the suspect is alive and only that link is bad.

All-to-all heartbeats grow with the square of the cluster size. Gossip spreads membership information with a fixed number of messages per node, scaling to thousands of nodes.

Treat it as a suspicion: fail over in a way that's safe even if the node is alive, using fencing and idempotent operations, rather than assuming it's gone.