Every distributed algorithm eventually has to decide that a peer is gone and carry on without it. In an asynchronous system that decision can never be certain: a node that has not answered may be crashed, paused in garbage collection, overloaded, or unreachable across a partition. A failure detector is the component that turns this uncertainty into a usable verdict, and the quality of that verdict determines how quickly a cluster fails over and how often it fails over by mistake.

This chapter covers the properties a detector should have, the simple heartbeat and ping designs most systems start with, the timeout-free and outsourced variants that work around unreliable direct links, the phi-accrual detector used by Cassandra and Akka that replaces a binary verdict with a suspicion level, gossip-based detection, and FUSE, which reverses the problem by guaranteeing that failure notifications reach everyone.

In one minute

• A failure detector is a local module that reports which peers it suspects have failed. Algorithms consult it to exclude dead nodes and keep making progress (liveness) without breaking their guarantees (safety).
• The two properties to balance are completeness (every real failure is eventually detected by every correct process) and accuracy (no correct process is wrongly suspected). Perfect accuracy is impossible asynchronously, so detectors trade accuracy for speed (efficiency).
• Heartbeats (the monitored node announces it is alive) and pings (the monitor asks) both rely on a timeout. Pick it too short and you get false positives; too long and failover is slow.
• Distinguish dead (certainly stopped) from suspected (not answering, status unknown). Most detectors only ever know the second.
• The timeout-free detector passes heartbeats along paths and counts them, so a node reachable only indirectly is still considered alive.
• Outsourced heartbeats ask neighbours to probe a suspected node before convicting it, filtering out one-sided link problems.
• The phi-accrual detector models heartbeat inter-arrival times as a distribution and outputs phi, a suspicion level where phi = n means roughly a 10 to the power of minus n chance of being wrong; the application chooses the threshold.
• Gossip-based detection piggybacks heartbeat counters on gossip messages so every node learns about every other node's liveness without direct probing.
• FUSE turns detection into notification: processes form groups, any member failure is converted into a group failure that every member is guaranteed to learn about.

What a failure detector must provide

Dead versus suspected

Petrov separates two vocabularies. A process that has stopped executing is dead, failed or crashed. A process that is not responding is unresponsive, faulty or slow, and is at most suspected: it might be dead, or it might be alive and merely unreachable or late. Because an observer only sees the absence of messages, every practical detector produces suspicions, not certainties. Treating a suspicion as certainty is where split-brain and double-leader incidents begin.

Role in the algorithm

A failure detector is a local subsystem: each node runs its own and the outputs of different nodes may disagree. Its purpose is to let the surrounding algorithm (replication, consensus, leader election) exclude unresponsive participants so that the algorithm keeps terminating. Chandra and Toueg formalised this: an "unreliable" failure detector that is only eventually accurate is enough to solve consensus in an asynchronous system, which is how practical protocols escape the FLP result from chapter 8.

Liveness and safety

Two algorithm properties frame the design:

• Liveness: something intended eventually happens. A detector contributes liveness by eventually reporting real failures so the algorithm stops waiting for a dead node.
• Safety: nothing unintended happens. A detector must not cause the algorithm to violate its invariants, for example by letting two nodes act as leader at once. In practice safety is guaranteed by the algorithm (quorums, epochs), not by the detector, precisely because the detector can be wrong.

Completeness and accuracy

The two formal properties of a detector, from Chandra and Toueg:

Property	Meaning	Strong form	Weak form
Completeness	Crashed processes are eventually suspected	Every correct process eventually suspects every crashed process	At least one correct process eventually suspects every crashed process
Accuracy	Correct processes are not suspected	No correct process is ever suspected by anyone	Eventually, correct processes stop being suspected (eventual accuracy)

Completeness is cheap: suspect everyone you have not heard from, and you will eventually suspect every dead node. Accuracy is the expensive one, because distinguishing slow from dead requires knowing message delays, which an asynchronous system does not provide. The useful detector classes therefore combine strong completeness with eventual weak accuracy: they may make mistakes but eventually stop suspecting nodes that are alive. That class is sufficient for consensus.

Efficiency and the fundamental trade-off

Efficiency is how quickly a detector identifies a failure. Efficiency and accuracy pull in opposite directions: a detector that convicts after a short silence detects crashes fast but misfires on slow nodes; one that waits longer is more accurate but slower. The book's conclusion is blunt: a detector cannot be both maximally accurate and maximally efficient. The parameters are tuned per system, and the better detectors (phi-accrual) expose the trade-off as a continuous knob rather than hiding it in a fixed timeout.

Heartbeats and pings

Two directions of the same idea

Both techniques probe liveness periodically and differ only in who initiates:

• Ping: the monitoring process sends a message to the monitored process and waits for a reply. No reply within the timeout means the target is suspected.
• Heartbeat: the monitored process periodically announces "I am alive" to its monitors. A monitor that has not received a heartbeat within the timeout suspects the sender.

Heartbeats are generally cheaper (one message per interval instead of two) and are the dominant pattern: Raft leaders heartbeat followers, Kafka consumers heartbeat the group coordinator, Cassandra nodes gossip heartbeats every second.

The timeout problem

A fixed timeout bakes in an assumption about network delay and process speed. In a partially synchronous system that assumption is wrong some of the time:

• Too short: a garbage collection pause, a burst of disk I/O or a congested link produces a false positive. The cost is an unnecessary failover, which in leader-based systems means a period of unavailability and sometimes a "flapping" leader.
• Too long: a real crash goes unnoticed for the whole timeout. Clients see errors or stale reads until the detector catches up.

A common mitigation is to require several missed heartbeats rather than one, which averages out single-interval noise at the cost of proportionally slower detection.

Limits of direct probing

Direct heartbeats and pings have a second weakness: they only measure the link between the monitor and the target. If that one link is slow or broken while the target is reachable from every other node, the monitor convicts a perfectly healthy process. Several of the designs below exist to incorporate other nodes' views.

Detectors that use other nodes' views

Timeout-free failure detector

Aguilera, Chen and Toueg proposed a heartbeat-based detector that uses no timeouts at all, designed for asynchronous systems where timeouts are meaningless. Instead of asking "has it been too long?" it asks "is the heartbeat count for this node still increasing?".

Heartbeat paths and counters

Each process keeps a list of neighbours and a counter per neighbour. Processes periodically send heartbeats to their neighbours, and each heartbeat carries the path it has travelled so far: the list of processes that have forwarded it.

On receiving a heartbeat, a process:

1. Increments the counter of every process that appears in the heartbeat's path (all of them demonstrably executed a step recently).
2. Appends itself to the path.
3. Forwards the heartbeat to each neighbour that is not already in the path.

What it buys

A process whose counter keeps growing is alive, even if no direct message from it has arrived, because its heartbeats are reaching the observer through intermediaries. This correctly treats a node with a broken direct link as alive, which a point-to-point timeout cannot do. The output is not "dead" or "alive" but a counter that the algorithm interprets: a node whose counter has stalled relative to the others is the one to suspect. The design is timeout-free in the sense that correctness does not depend on choosing a delay; it depends only on the counters' relative progress.

Outsourced heartbeats

A cheaper way to get other nodes' perspective is to outsource the probe. When a process suspects a peer after a missed heartbeat, instead of convicting immediately it asks some of its neighbours to ping the suspect on its behalf. If any neighbour gets a reply, the suspect is alive and the original monitor has a one-sided link problem. If none do, the suspicion is far better founded.

This pattern, used by the SWIM protocol and by Serf and Consul, has two benefits: it reduces false positives caused by a single bad link, and it means a process does not need to monitor every other process directly. Each process only tracks a subset of peers and relies on the group to cover the rest, which keeps per-node heartbeat traffic constant as the cluster grows.

Phi-accrual failure detector

From a binary verdict to a suspicion level

Hayashibara, Défago, Yared and Katayama observed that a detector with a fixed timeout fuses two decisions that should be separate: estimating how likely a failure is, and deciding what to do about it. Their phi-accrual failure detector (2004) outputs a continuous value, phi, that expresses how suspicious the current silence is. The application reads phi and applies its own threshold, and different components can use different thresholds on the same measurement: a load balancer might stop routing at a low phi, while a leader-election module waits for a much higher one before triggering an election.

Computing phi

The detector keeps a sliding window of recent heartbeat arrival times from each monitored peer and computes the inter-arrival intervals. From the window it estimates the distribution of intervals (the paper uses a normal distribution with the sample mean and variance). Given the time since the last heartbeat, it computes the probability that the next heartbeat would arrive even later than that, and converts it to a log scale:

t_now           current time
t_last          arrival time of the most recent heartbeat
P_later(t)      probability that an inter-arrival gap exceeds t,
                i.e. 1 - CDF(t) under the estimated distribution

phi(t_now) = -log10( P_later(t_now - t_last) )

Interpreting phi

Because phi is a negative base-10 logarithm of a probability, each unit of phi is a tenfold drop in the probability that the node is actually fine:

phi	P_later	Reading
1	10%	One in ten chance a live node is this late; too noisy to act on
2	1%	Moderate suspicion
3	0.1%	Strong suspicion
8	0.000001%	Default convict threshold in Cassandra (phi_convict_threshold) and Akka Cluster
12	10 to the power of minus 12	Very conservative; used when false positives are expensive (unstable networks, some cloud deployments)

Phi grows continuously as the silence lengthens and snaps back to zero when a heartbeat arrives, so a node that is late by a little produces a small phi, and the same absolute delay produces a very different phi in a cluster with tight, regular heartbeats than in one with jittery heartbeats. That is the point: the detector adapts to observed conditions instead of a hand-tuned constant.

Worked example

Suppose a peer heartbeats roughly every 1,000 ms and the window shows a mean interval of 1,000 ms with a standard deviation of 100 ms. The current silence is 1,300 ms.

1. The silence is 3 standard deviations past the mean. Under a normal distribution, P_later(1,300 ms) is about 0.00135.
2. phi = -log10(0.00135) is about 2.9. If the application threshold is 8, the node is still considered alive, though a load balancer might deprioritise it.
3. At 1,500 ms (5 standard deviations) P_later is about 3 times 10 to the power of minus 7 and phi is about 6.5. Still below 8.
4. At roughly 1,600 ms phi crosses 8 and the node is convicted. Note how a stable heartbeat history makes conviction fast, about 0.6 s beyond the expected interval.

Now suppose the network is jittery and the standard deviation is 400 ms with the same mean. The same 1,500 ms silence is only 1.25 standard deviations late, P_later is about 0.1, and phi is about 1. Conviction at phi = 8 would need a silence of over 3 s. The detector has automatically become more patient because it has learnt that this peer is often late.

Cassandra's implementation simplifies the model: instead of a normal distribution it uses an exponential distribution driven by the mean interval, under which phi grows linearly with the silence (phi equals the silence divided by the mean, divided by the natural log of 10). It also clamps the minimum interval and ignores pathologically large ones so that a single long GC pause does not permanently inflate the window. Akka adds an explicit acceptable-heartbeat-pause margin that is added to the expected interval, so a known-tolerable pause (a GC cycle) does not push phi over the threshold.

Why it is popular

The phi-accrual detector separates measurement from policy, adapts to network conditions, costs no more than ordinary heartbeats, and gives operators one knob whose meaning (orders of magnitude of false-positive risk) does not change with hardware or load. Its weakness is the window: a fresh node has no history, so implementations seed it with a default interval, and the detector assumes recent intervals predict the next one.

Gossip and failure detection

Heartbeat counters on gossip

Van Renesse, Minsky and Hayden's gossip-style failure detection drops direct monitoring entirely. Each process maintains, for every known member, a heartbeat counter and the local timestamp at which that counter last increased. Periodically, each process increments its own counter and gossips its whole table to one or a few randomly chosen peers. The receiver merges tables, keeping the higher counter for each member and refreshing that member's local timestamp whenever the counter rose.

If a member's counter has not increased for longer than a threshold at a given observer, that observer suspects it. Because tables spread epidemically, information about a live node's counter reaches every member in O(log n) gossip rounds, and so does the fact that a counter has stalled.

Properties

• No direct link required: a node is deemed alive if anyone has heard from it recently, so one-sided link failures do not cause false positives.
• Scales well: each node sends a constant number of messages per round regardless of cluster size, at the cost of each message carrying O(n) counters. Cassandra's gossiper bounds this by exchanging digests first.
• Detection latency is probabilistic: a crashed node is detected only after its counter has stalled across the cluster for the threshold, which is longer than a direct timeout. Gossip trades speed for robustness and scalability.
• Membership and detection converge: the same mechanism distributes who is in the cluster, their states and schema versions, which is why Cassandra, Riak and Dynamo-style systems build detection into gossip rather than alongside it.

Cassandra combines the two ideas in this chapter: gossip carries heartbeat generation and version numbers, and each node feeds the arrival times of gossip updates about a peer into a phi-accrual detector for that peer.

Reversing the problem: the FUSE failure notification service

A different guarantee

All the detectors above answer "do I think X failed?" and leave it to the algorithm to propagate that belief. Propagating failure information is itself a distributed problem: notifying everyone is expensive, and during a partition it may be impossible to reach some processes at all. FUSE (Dunagan, Harvey, Jones, Kostić, Theimer and Wolman, 2004) reverses the problem statement: rather than detecting failures accurately, it guarantees that if a failure is signalled, every participant learns of it, even across partitions.

Groups and deliberate silence

An application creates a FUSE group containing the processes that depend on each other. Within the group:

• Members periodically ping one another along a spanning structure.
• A member that stops receiving pings from a peer for too long stops responding to pings itself, deliberately.
• Any member may also explicitly signal a failure.

The effect is that one process's failure, or one broken link, converts into a group failure: silence spreads through the group until every member observes it. Every member then delivers a failure notification to the application, which typically tears down the group and rebuilds a new one from the members it can still reach.

Why the conversion matters

The guarantee is one-sided but strong: FUSE never leaves some members believing the group is intact while others have declared it failed. It may convert a single transient link hiccup into a full group failure, a cost in false positives, but it produces agreement on the failure, which detectors based on individual timeouts cannot. It works under any pattern of crashes, disconnects and partitions, which is exactly where ad hoc "tell everyone" notification breaks down.

Design trade-offs

Technique	Detection speed	False positives	Per-node cost	Needs direct link to target	Best fit
Ping with fixed timeout	Fast if timeout is short	High when timeout is short	2 messages per peer per interval	Yes	Small clusters, stable LAN
Heartbeat with fixed timeout	Fast	Same trade-off as ping	1 message per monitor per interval	Yes	Leader-follower systems (Raft, Kafka)
Multiple missed heartbeats	Slower by the multiple	Lower	Same	Yes	Cheap robustness upgrade
Timeout-free (path counters)	Depends on counter divergence	Low for link failures	Heartbeats fan out along paths	No	Asynchronous settings, unreliable links
Outsourced heartbeats (SWIM style)	One extra round when suspected	Low	Constant per node	No	Large membership clusters (Consul, Serf)
Phi-accrual	Adapts to observed jitter	Tunable via threshold	Same as heartbeats plus a window	Yes, or fed from gossip	Cassandra, Akka, anything with variable latency
Gossip-based	Slower, O(log n) rounds	Low for link failures	Constant messages, O(n) payload	No	Dynamo-style membership
FUSE	Group-level, propagates to all	Converts link faults to group faults	Pings within group	No	Groups needing agreed failure semantics

Choosing: a leader-based consensus system wants fast detection of the leader with a modest tolerance for false positives (an unnecessary election costs seconds of availability, not correctness, because terms protect safety). A large eventually consistent store wants scalability and few false positives, so gossip plus phi-accrual is the standard answer. A system that cannot tolerate split views of membership chooses FUSE-like all-or-nothing semantics and accepts over-reporting.

Interview angle

• Can a failure detector ever be certain a node has crashed? No, not in an asynchronous system. Silence is consistent with crash, slowness or partition, and no local observation distinguishes them. Detectors produce suspicions, and the algorithms around them (leases, epochs, quorums) must remain safe when a suspicion is wrong.

• Define completeness and accuracy for a failure detector and explain which one is hard. Completeness: every crashed process is eventually suspected by correct processes. Accuracy: correct processes are not suspected. Completeness is trivial (suspect anyone who is silent). Accuracy is impossible to guarantee without timing bounds, so practical detectors aim for eventual accuracy: they may misfire but eventually stop suspecting live nodes.

• How does the phi-accrual detector improve on a fixed timeout? It records heartbeat inter-arrival times, estimates their distribution and outputs phi = -log10 of the probability that a live node would be this late. The threshold then has a stable meaning (phi = 8 means about a one in a hundred million chance of a false positive) regardless of network conditions, and the detector automatically becomes more patient when heartbeats are jittery and stricter when they are regular.

• What goes wrong if a failure detector is too aggressive in a leader-based system? Followers suspect a healthy leader during a GC pause and start an election. The old leader is deposed, the cluster is unavailable for the election, and if the pause ends the old leader may briefly believe it is still in charge. Safety survives only because terms or epochs let the cluster reject its stale writes; availability and tail latency suffer, and repeated misfires produce leader flapping.

• How does gossip-based failure detection scale compared with every node pinging every other node? All-pairs pinging is O(n squared) messages per round. Gossip sends a constant number of messages per node per round, with tables of size O(n), and information reaches everyone in O(log n) rounds. The cost is higher and probabilistic detection latency.

• Why would you ask neighbours to ping a suspect before declaring it dead? A missed heartbeat only proves the direct link or the monitor's own view is bad. Indirect probes through other nodes separate "the node is dead" from "my link to it is bad", cutting false positives substantially. This is the core of SWIM, used by Consul and Serf.

• Design a failure detector for a 500-node storage cluster across three availability zones. Use gossip for membership so no node tracks all others directly; feed heartbeat arrival times into a per-peer phi-accrual detector with a conservative threshold (8 to 12) and an explicit acceptable pause for GC; use indirect probes before conviction; separate thresholds for "stop routing reads here" (low phi) from "rebalance data away" (high phi plus a sustained period) to avoid expensive reactions to transient blips.

Pitfalls and misconceptions

• "A timeout means the node is dead." It means you have not heard from it. Build the rest of the system (leases, fencing, quorums) so that acting on a wrong suspicion cannot corrupt state.
• "Lower the timeout to fail over faster." Lower timeouts raise false positives, and each false positive costs an election or a rebalance. Tune against observed latency distributions, which is what phi-accrual does for you.
• "Phi is a probability." Phi is the negative log10 of a probability; phi = 8 corresponds to a 10 to the power of minus 8 chance of being wrong, not to 8% or 80%.
• "Gossip detection is fast." It is scalable and robust, not fast. Convergence takes O(log n) rounds, and the suspicion threshold adds to that. Systems needing sub-second leader failover use direct heartbeats.
• "If my node can't reach X, X is down." Your link may be the problem. Outsourced heartbeats and the timeout-free path-counter detector exist precisely to separate link failure from node failure.
• "FUSE is a better failure detector." FUSE is a failure notification service with all-or-nothing semantics. It deliberately over-reports (a link fault becomes a group fault) in exchange for guaranteeing that every member agrees a failure happened.
• "The failure detector guarantees safety." It contributes to liveness. Safety is the algorithm's job; a correct algorithm stays safe under arbitrarily wrong detector output and merely stalls.

Key terms

Term	Meaning
Failure detector	A local subsystem that reports which peers it suspects have failed, so algorithms can exclude them
Dead / crashed	A process that has stopped executing; a certainty an observer rarely has
Suspected / unresponsive	A process that has not answered in time; may be dead, slow or partitioned
Completeness	Every crashed process is eventually suspected (strong: by every correct process; weak: by at least one)
Accuracy	Correct processes are not wrongly suspected; eventual accuracy means mistakes stop eventually
Efficiency	How quickly a detector reports a real failure; traded against accuracy
Liveness	The guarantee that intended events eventually happen (a failure is eventually noticed)
Safety	The guarantee that unintended events never happen; preserved by the algorithm, not the detector
Heartbeat	A periodic "I am alive" message from the monitored process to its monitors
Ping	A periodic probe from the monitor that expects a reply
Timeout-free failure detector	Aguilera, Chen and Toueg's design in which heartbeats carry paths and liveness is read from growing counters
Outsourced heartbeat	Asking neighbours to probe a suspect indirectly before convicting it (SWIM)
Phi-accrual failure detector	A detector that outputs a suspicion level phi = -log10 of the probability a live node would be this late
Inter-arrival distribution	The empirical distribution of gaps between heartbeats, kept in a sliding window
Convict threshold	The phi value above which an application treats a node as failed (8 by default in Cassandra and Akka)
Gossip-based failure detection	Heartbeat counters merged epidemically; a stalled counter indicates failure
Heartbeat counter	A per-member monotonically increasing value whose progress proves liveness
FUSE	A failure notification service that converts any member or link failure into a group failure every member learns about

Further reading

• Database Internals, Chapter 9.
• Chandra, Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems", JACM 1996: https://doi.org/10.1145/226643.226647
• Hayashibara, Défago, Yared, Katayama, "The Phi Accrual Failure Detector", SRDS 2004.
• Aguilera, Chen, Toueg, "Heartbeat: A Timeout-Free Failure Detector for Quiescent Reliable Communication", WDAG 1997.
• Van Renesse, Minsky, Hayden, "A Gossip-Style Failure Detection Service", Middleware 1998.
• Das, Gupta, Motivala, "SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol", DSN 2002.
• Dunagan, Harvey, Jones, Kostić, Theimer, Wolman, "FUSE: Lightweight Guaranteed Distributed Failure Notification", OSDI 2004.
• Apache Cassandra documentation on gossip and phi_convict_threshold; Akka Cluster documentation, "Failure Detector" section.
• Kyle Kingsbury's distributed systems class notes: https://github.com/aphyr/distsys-class