Distributed Systems #7
Distributed Systems Part-7 (Failure Detection and Fault Tolerance)
Failure detection and fault tolerance in distributed systems

On this page
Part 7: Failure Detection and Fault Tolerance
In Part 6, we saw how data gets spread across many nodes so that no single machine has to carry the whole load. But spreading data across more machines also means more things that can fail, and failing quietly is often worse than failing loudly. This part is about a question that sounds simple but turns out to be surprisingly deep, how does a distributed system actually know when a node is dead.
Why failure detection is hard
Go back to Part 1 for a moment. In an asynchronous network, there is no upper bound on how long a message can take to arrive. This means that if you send a message to a node and get no response, you genuinely cannot tell whether that node crashed, whether the node is just slow, or whether the network dropped your message, or the reply, somewhere along the way. All three situations look identical from where you are standing.
This is not a minor inconvenience; it is a fundamental limit. No failure detector can be perfectly accurate in an asynchronous system, because accuracy would require knowing something that is genuinely unknowable, whether a silent node is dead or just slow. Every practical failure detector accepts this limit and makes a tradeoff instead, usually between detecting failures quickly and avoiding false alarms.
Heartbeats
The simplest and most widely used failure detection mechanism is the heartbeat. Every node periodically sends a small message to the others, essentially saying "I am still alive." If a node stops sending heartbeats for some period of time, the other nodes assume it has failed.
This sounds almost too simple to be worth discussing, but the details matter a lot in practice:
- Timeout too short: you will get false positives, declaring healthy nodes dead just because a heartbeat got delayed by normal network jitter or a brief garbage collection pause.
- Timeout too long: real failures take longer to detect, which means longer periods where the system keeps sending work to a node that is actually gone.
This tension is not a bug in any particular implementation, it is the same fundamental tradeoff we just described, showing up in its most basic form. A fixed timeout is a single number trying to capture a decision that really depends on constantly changing network conditions.
Phi accrual failure detectors
Because a single fixed timeout is such a blunt tool, some systems use a more adaptive approach called a phi accrual failure detector, first described in a 2004 paper by Hayashibara and colleagues, and now used by systems like Cassandra and Akka.
Instead of producing a simple yes or no answer about whether a node is alive, a phi accrual detector produces a continuously changing suspicion level, usually called phi. This value is calculated based on the history of recent heartbeat arrival times from that specific node. If heartbeats have been arriving fairly regularly every second, and suddenly two seconds pass with nothing, phi rises to reflect growing suspicion. If that same node has always had somewhat irregular heartbeats, arriving anywhere between half a second and two seconds apart, the same two-second gap raises phi much less, since it is within the normal range of behaviour already observed for that node.
Phi is on a logarithmic scale, which makes it easy to reason about. Roughly speaking, a phi of 1 means about a 10% chance that declaring the node dead right now would be a mistake, a phi of 2 means about 1%, and a phi of 3 means about 0.1%. Cassandra's default is to convict a node once phi passes 8.
The real benefit here is that the detector adapts itself to each node's own normal behaviour and to current network conditions, rather than applying one arbitrary threshold to every node in the cluster regardless of context. Applications can then decide their own threshold for phi, choosing to react quickly and accept more false positives, or wait longer and reduce false alarms, depending on what a false positive actually costs them.
Gossip protocols
Heartbeats and phi accrual detectors both describe how a node figures out whether one other node is alive. But in a cluster with hundreds or thousands of nodes, having every node directly monitor every other node does not scale, since the number of connections needed grows with the square of the cluster size: a thousand nodes would mean close to a million monitoring pairs.
Gossip protocols solve this by spreading information the way rumours spread through a group of people. Periodically, each node picks a small number of other random nodes and exchanges information with them, including what it currently believes about the health of every node it knows about. Over successive rounds, this information spreads exponentially through the cluster, since every node that learns something new starts spreading it further on the next round. In practice, news reaches the whole cluster in a number of rounds that grows only with the logarithm of the cluster size, so doubling the cluster adds roughly one more round.
Round 0: 1 node knows "Node 7 is down"
Round 1: ~3 nodes know
Round 2: ~9 nodes know
Round 3: ~27 nodes know … the whole cluster within a few seconds
This approach scales far better than direct monitoring, since each node only needs to talk to a handful of others at a time, not the entire cluster. It is also naturally resilient, since there is no single node responsible for tracking everyone's health, so no single failure can blind the rest of the cluster to what is happening. Cassandra uses gossip specifically for this purpose, letting nodes learn about failures and cluster membership changes without any centralized coordinator being involved. (The Key-Value Store design shows gossip doing this job inside a full system.)
The tradeoff is that gossip-based information is inherently a little stale. Since it takes a few rounds for news to fully propagate, different nodes can briefly disagree about which nodes are up or down, which is a form of the eventual consistency we discussed back in Part 4, just applied to cluster membership information instead of application data.
Split brain
Now for the scenario that failure detection exists partly to prevent, and partly to sometimes cause by mistake. Split brain happens when a network partition splits a cluster into two or more groups that can each talk to nodes within their own group, but cannot talk to nodes in the other group.
The danger is that each side of the partition, unable to see the other side, may conclude the other side is dead and proceed to elect its own leader or otherwise keep operating independently. Now you have two parts of what used to be one system, both believing they are in charge, both potentially accepting writes, with no way to reconcile the two until the partition heals. By the time it does heal, you may have two conflicting versions of the truth that need to be manually or automatically resolved, which connects directly back to the conflict resolution problems we covered with multi-leader replication in Part 3.
This is exactly why consensus algorithms like the ones from Part 5 require a majority to make progress, rather than allowing any group of nodes to act unilaterally. If a network partition splits a five node cluster into a group of three and a group of two, only the group of three can reach a majority, and only that group is allowed to elect a leader or commit new operations. The group of two is deliberately left unable to make progress on its own, which feels restrictive, but it is precisely what prevents split-brain from happening in a properly designed consensus-based system. This is the direct payoff of the majority overlap property we discussed back in Part 5, applied to the real-world scenario it was designed to prevent.
5-node cluster, partition splits it 3 | 2
Side A: Nodes 1, 2, 3 → 3 of 5 is a majority → elects a leader, keeps working
Side B: Nodes 4, 5 → 2 of 5 is not → refuses writes until it heals
There is one more subtlety. An old leader stuck on the minority side may not know it has been replaced, and could still try to write to shared storage. The usual protection is a fencing token: every new leader gets a higher number (Raft's term works this way), every write carries that number, and storage rejects any write carrying a number lower than one it has already seen.
Self-healing systems
Good distributed systems are not just designed to detect failure; they are designed to recover from it automatically wherever possible, since waking up a human at three in the morning for every single node failure does not scale any better than the systems themselves would without automation.
This usually combines several of the ideas from this series so far:
- Failure detection, through heartbeats or gossip, identifies that something has gone wrong.
- Replication, from Part 3, means the data that lived on the failed node still exists elsewhere.
- Consensus, from Part 5, allows the cluster to safely agree on a new leader or a new arrangement of responsibilities without risking split-brain.
- Rebalancing, from Part 6, moves data and load around to compensate for the node that is now missing, restoring a healthy distribution across whatever nodes remain.
None of these pieces works particularly well in isolation. The real strength of a fault-tolerant system comes from how these individual mechanisms are combined, each one covering a gap the others leave open.