Failure Detection in Distributed Systems: Heartbeats, Timeouts and the Phi Accrual Detector

by
Home » Distributed Systems » Fault Tolerance & High Availability » Failure Detection in Distributed Systems: Heartbeats, Timeouts and the Phi Accrual Detector

Distributed Systems Series — Part 4.4: Fault Tolerance & High Availability

The Question That Has No Perfect Answer

When a distributed node stops responding, other nodes face a question that cannot be answered with certainty: has this node failed, or is it merely slow?

In a single-machine system, this question does not exist. The operating system knows precisely which processes are running and which have terminated. In a distributed system, nodes communicate over networks that can drop packets, introduce variable latency, and partition without warning. A node that appears dead may be processing a large garbage collection pause. A node that appears alive may have crashed after its last heartbeat. Silence is always ambiguous.

This is not a solvable engineering problem — it is a fundamental property of asynchronous distributed systems, formalised in the FLP impossibility result covered in Post 3.6. No failure detector in an asynchronous system can simultaneously guarantee that it always suspects failed nodes (completeness) and never suspects healthy nodes (accuracy). Every production failure detection mechanism makes a trade-off between these two properties.

The consequences of getting this trade-off wrong are severe. A failure detector that is too aggressive triggers unnecessary leader elections in Raft clusters, causing measurable availability gaps and potential brief split-brain windows. A failure detector that is too conservative leaves genuinely failed leaders in place, blocking writes until the slow detection resolves. Failure detection tuning is not an operational detail — it is a correctness and availability decision.

This post covers the failure detection mechanisms used in production distributed systems — from simple heartbeats and timeouts through the phi accrual failure detector used by Cassandra and Akka, through gossip-based failure propagation used by Consul and Kubernetes. It connects directly to the failure taxonomy established in Post 4.1 — failure detection is the mechanism that translates crash-stop, crash-recovery, and timing failures into actionable signals for higher-level protocols.

What Failure Detectors Actually Provide

Chandra and Toueg’s 1996 paper “Unreliable Failure Detectors for Reliable Distributed Systems” introduced the formal characterisation of failure detectors that every subsequent distributed systems text — Tanenbaum, Coulouris, Kleppmann, Vitillo — builds on. A failure detector is a mechanism that monitors nodes and produces suspicions. It outputs either “suspect” or “alive” for each monitored node. It does not guarantee correctness — it provides probabilistic hints that higher-level protocols use to make decisions.

Two properties characterise failure detector quality:

Completeness means the failure detector eventually suspects every node that has actually failed. A failure detector with weak completeness may miss failures entirely or detect them only after an arbitrarily long delay. Strong completeness guarantees that every failure is eventually detected. Without completeness, a failed leader could remain in place indefinitely.

Accuracy means the failure detector does not suspect healthy nodes. A failure detector with strong accuracy never triggers false alarms. A failure detector with weak accuracy may suspect healthy nodes temporarily. Without accuracy, the system triggers unnecessary failovers and leader elections for nodes that are merely slow.

The fundamental trade-off: in an asynchronous network with variable latency, completeness and accuracy conflict. A detector aggressive enough to always detect failures quickly will also suspect healthy nodes during latency spikes. A detector conservative enough to never suspect healthy nodes will be slow to detect real failures. Production systems tune this trade-off based on their specific availability and correctness requirements.

An important scope note: failure detectors are designed for crash-stop, crash-recovery, omission, and timing failures — the failure classes from Post 4.1 that manifest as absence or slowness of communication. They are not designed for Byzantine failures (a node sending incorrect messages) or gray failures (a node responding correctly to health checks while producing wrong results for application requests). Gray failure detection requires application-level monitoring, covered in Post 4.8.

Heartbeats: The Foundational Mechanism

The simplest failure detection mechanism is the heartbeat: periodic messages that nodes send to indicate they are alive. Nodes that stop sending heartbeats are suspected of having failed.

Two architectural variants exist. In push heartbeats, each node periodically sends a “I am alive” message to its monitors — the monitoring nodes wait for these messages and raise an alarm when they stop arriving. In pull heartbeats (also called polling), the monitoring node periodically asks the monitored node “are you alive?” — the monitored node responds if it can, and the monitoring node suspects failure if it does not receive a response within a timeout.

Push heartbeats are more efficient at scale — each monitored node sends one message to each monitor, producing N×M messages for N monitored nodes and M monitors. Pull heartbeats require the monitoring node to send a request and wait for a response, which doubles the message count and adds the monitoring node’s polling interval to the detection latency. Pull heartbeats are however more resilient to monitoring node failures — if the monitor crashes and stops polling, the monitored node is not falsely declared failed.

Kubernetes uses a hybrid: each node’s kubelet pushes heartbeat status updates to the Kubernetes API server (a Node Lease object in the `kube-node-lease` namespace) every 10 seconds by default. The node controller on the control plane monitors these leases and marks a node as NotReady if it has not received a heartbeat for 40 seconds (the `node-monitor-grace-period`). After the node remains NotReady for 5 minutes (the `pod-eviction-timeout`), pods on the node are evicted and rescheduled. These defaults are deliberately conservative — they prioritise accuracy (not falsely evicting pods from temporarily slow nodes) over fast detection.

Fixed Timeouts: Simple but Brittle

A timeout converts missing heartbeats into a failure suspicion. If a heartbeat has not arrived within T seconds of the last one, the monitoring node suspects failure. Simple, widely deployed, and easy to reason about.

The problem is that fixed timeouts assume stable network conditions. In production cloud environments, network latency is variable — it depends on load, routing changes, noisy neighbours, and transient congestion. A timeout value tuned for average conditions will produce false positives during latency spikes and too-slow detection during network degradation.

The cost of a false positive in a Raft cluster is concrete and measurable. When a follower suspects the leader has failed due to a timeout during a GC pause or network congestion, it starts an election. If the old leader is still alive, both the old leader and the new candidate believe they are entitled to leadership simultaneously — a brief split-brain window. Raft prevents writes from completing during this window (neither the old leader, which has lost quorum, nor the new candidate, which has not yet been elected, can commit writes). The cluster is unavailable for the duration of the election, typically 150 to 300 milliseconds in a well-tuned cluster. For a system with 99.99% availability target and a 4.4-minute monthly error budget, one unnecessary election per week consumes approximately 5% of the monthly budget.

Timeout tuning guidance for fixed-timeout systems: set the timeout to at least the 99th percentile network round-trip time plus a multiple of the heartbeat interval. For a system with heartbeat interval H and p99 network latency L, the timeout T should be at minimum T = L + 2×H. For a single-region deployment with 10ms p99 latency and 1-second heartbeat interval, T = 12 seconds minimum. For a cross-region deployment with 100ms p99 latency and 1-second heartbeat interval, T = 102 seconds minimum — which means failure detection takes nearly two minutes, which may be unacceptably slow. This is why cross-region systems use gossip protocols or adaptive detectors rather than fixed timeouts.

The Phi Accrual Failure Detector

The phi accrual failure detector, introduced by Hayashibara et al. in 2004, replaces the binary alive/dead classification of fixed timeouts with a continuous suspicion level. Instead of asking “has the heartbeat timed out?” it asks “how statistically surprising is the absence of a heartbeat given the historical heartbeat arrival pattern?”

The key insight is that heartbeat intervals follow a statistical distribution — not a fixed value. On a normally loaded network, heartbeats arrive with some average interval and some variance. During periods of congestion or load, intervals increase and their distribution changes. The phi detector models this distribution and uses it to interpret the significance of a delayed heartbeat. A delay that is one standard deviation above the mean is mildly suspicious. A delay that is five standard deviations above the mean is highly suspicious. The same delay means different things in different network conditions.

How it works in practice: the detector maintains a sliding window of recent heartbeat arrival times — typically the last 1,000 heartbeats. From this window, it calculates the mean (μ) and standard deviation (σ) of heartbeat intervals. When checking whether a node has failed, it measures the time elapsed since the last heartbeat (Δt) and calculates φ:

φ = –log₁₀(1 – F(Δt))

Where F is the cumulative distribution function of the heartbeat interval distribution — the probability that a heartbeat interval is less than or equal to Δt. Subtracting from 1 gives the probability that the interval exceeds Δt, and taking –log₁₀ converts this to the phi value.

Interpreting phi values concretely: φ = 1 means there is approximately a 10% probability that the node has failed given the observed delay. φ = 2 means approximately 1% probability. φ = 3 means approximately 0.1% probability. φ = 8 means approximately 0.000001% probability that a delay this large would occur from network variance alone — at this level, the node is almost certainly failed.

Cassandra uses φ = 8 as its default failure action threshold. Akka Cluster uses φ = 10 by default, which is more conservative (fewer false positives) at the cost of slightly slower detection. Both allow this threshold to be configured per deployment based on network conditions.

Why phi adapts to network conditions: if network latency increases due to congestion, heartbeat intervals increase and the detector observes this in its sliding window. The mean and variance of the distribution increase, which means a longer delay is now required to produce the same phi value. The detector automatically becomes more lenient during periods of network stress — exactly the opposite of a fixed timeout, which produces more false positives when the network is stressed.

This is the property shown in the diagram above: while a fixed timeout produces a binary jump from 0 to “failed” at the timeout boundary, phi rises gradually as delays increase, giving higher-level protocols early warning that something may be wrong without triggering immediate action. A system monitoring phi can choose to take pre-emptive action at φ = 5 (route traffic away from a suspect node) while waiting until φ = 8 to declare it fully failed and trigger leader election.

Gossip Protocols: Failure Detection at Scale

Direct heartbeat monitoring — where each node monitors every other node directly — does not scale to large clusters. In a cluster of N nodes, direct heartbeat monitoring requires O(N²) messages per heartbeat interval — each of N nodes sends heartbeats to each of the other N-1 nodes. At N=1,000, this is nearly one million messages per heartbeat interval.

Gossip protocols — also called epidemic protocols — solve this by having each node periodically share its knowledge of cluster state with a small random subset of other nodes. Knowledge of failures propagates through the cluster as each node gossips what it knows to a few neighbours, who in turn gossip to their neighbours. Information spreads like an epidemic — exponentially quickly, with very high probability of reaching every node within O(log N) rounds.

The SWIM protocol (Scalable Weakly-Consistent Infection-style Process Group Membership, Renesse et al. 2002) is the foundational gossip-based failure detection protocol. SWIM addresses a key weakness of simple gossip: the false positive problem. In simple gossip, if node A cannot directly reach node B, it suspects B has failed and gossips this suspicion. But B may be reachable through other nodes — the link between A and B is broken, not B itself.

SWIM’s solution: before suspecting B has failed, node A asks a random subset of other nodes to try to contact B on its behalf (indirect probing). If none of the indirect probes succeed either, B is then suspected. If any indirect probe succeeds, A knows the direct A→B link is broken but B is alive. This dramatically reduces false positives caused by one-directional network partitions or congested links between specific node pairs.

Consul uses a SWIM-based gossip protocol (the memberlist library) for cluster membership and failure detection. Each Consul agent sends direct probes and indirect probes, and gossips failure suspicions through the cluster. A node that fails to respond to both direct and indirect probes is marked suspicious; if it does not respond within a configurable suspicion timeout, it is declared dead and gossiped as such to the rest of the cluster.

Kubernetes uses a gossip-based approach for certain cluster-wide state propagation, though its primary node failure detection relies on the kubelet heartbeat mechanism described above. HashiCorp Serf — built on SWIM — is a standalone gossip cluster membership library used by Consul, Nomad, and other distributed systems that need scalable failure detection without the full weight of a consensus-backed coordination service.

How Failure Detection Integrates with Consensus

Failure detection is not standalone infrastructure — it is the trigger mechanism for the consensus algorithms covered in Post 3.7. The relationship is direct: failure detection fires → consensus protocol responds.

In Raft, follower nodes maintain an election timeout — a randomised timer (typically 150-300ms) that resets every time a heartbeat is received from the leader. If the election timeout expires without a heartbeat, the follower assumes the leader has failed and starts an election. The Raft election timeout is a fixed timeout failure detector with the specific characteristic that it is randomised — different followers time out at different moments, which prevents simultaneous elections and the vote-splitting that would result.

The interaction between the election timeout and the leader’s heartbeat interval is a critical tuning relationship. The heartbeat interval must be significantly smaller than the election timeout — typically by a factor of 10. If the heartbeat interval is 150ms and the election timeout is 150-300ms, any single delayed heartbeat can trigger an election. If the heartbeat interval is 15ms and the election timeout is 150-300ms, 10 consecutive missed heartbeats are needed to trigger an election, providing substantial buffer against transient network delays.

etcd’s default configuration uses 100ms heartbeat interval and 1000ms election timeout — a 10:1 ratio. In single-region deployments with sub-10ms network latency, this produces rare false elections. In cross-region deployments where network latency may be 100ms or more, a heartbeat interval of 100ms is within one network round-trip of the election timeout, making false elections common. Cross-region etcd deployments must increase both the heartbeat interval and election timeout by approximately the cross-region network latency.

Failure Detection During Network Partitions

Network partitions create the most challenging scenario for failure detection — nodes on each side of the partition cannot reach nodes on the other side, causing mutual false suspicion. Each side suspects the other has failed and may initiate recovery actions.

In a Raft cluster that is partitioned 3-2 (three nodes on one side, two on the other), the larger group can elect a new leader — it has quorum. The smaller group cannot elect a leader — it cannot reach a majority. The old leader, if it was on the smaller side, will detect that it can no longer commit writes (it cannot reach a quorum of followers) and step down. The failure detector on the larger side detects the old leader as unreachable and triggers an election. This is the correct behaviour — the system maintains safety by requiring quorum for both leader election and write commitment.

The danger is a partition that is exactly 50-50 in a system with an even number of nodes. In a 4-node Raft cluster, a 2-2 partition means neither side has a majority (quorum requires 3 of 4). Both sides detect the other as failed. Neither side can elect a leader. The system becomes completely unavailable for writes until the partition heals. This is why Raft clusters are deployed with odd numbers of nodes — 3 or 5 — so that any partition produces an unequal split that allows one side to achieve quorum.

Fencing tokens, introduced in Post 2.4, are the mechanism that prevents a partitioned old leader from accepting writes even if it does not know it has been replaced. When a new leader is elected, it receives a higher epoch number or fencing token. The storage backend rejects writes from the old leader because its token is lower than the new leader’s — even if the old leader does not yet know it has been replaced.

Production Tuning Reference

Starting values for failure detection tuning in three major systems:

Cassandra phi accrual detector: default phi threshold is 8, heartbeat interval is 1 second. For single-region deployments with stable networks, the defaults are well-calibrated. For multi-region or cloud deployments with higher latency variance, increase the phi threshold to 10-12 to reduce false positives, or increase the heartbeat interval to 2 seconds to give the detector more statistical samples before acting.

Akka Cluster phi accrual detector: default phi threshold is 10, heartbeat interval is 1 second, acceptable heartbeat pause is 3 seconds. The heartbeat pause setting prevents false detections during JVM GC pauses — if the monitored node does not send a heartbeat for up to 3 seconds due to GC, the detector does not increase phi. Set this to at least the 99th percentile GC pause time for your application.

etcd / Raft: default heartbeat interval is 100ms, election timeout is 1000ms. For cross-region deployments, set heartbeat interval to approximately 1× the cross-region round-trip latency and election timeout to 10× the heartbeat interval. For US-EU deployments with 100ms RTT, use heartbeat interval 200ms and election timeout 2000ms.

Kubernetes node monitoring: default node-monitor-grace-period is 40 seconds, pod-eviction-timeout is 5 minutes. For environments where faster pod rescheduling is required, reduce node-monitor-grace-period to 20 seconds and pod-eviction-timeout to 2 minutes. Be aware that more aggressive settings increase the risk of unnecessary pod evictions during transient node slowness.

Key Takeaways

  1. Failure detection is fundamentally uncertain in asynchronous distributed systems — it is impossible to distinguish a crashed node from a slow node with certainty, so all failure detectors make a trade-off between completeness (detecting all failures) and accuracy (avoiding false suspicions)
  2. Fixed timeouts are simple but brittle — they assume stable network conditions and produce more false positives as network variance increases, which is exactly when production systems are already under stress
  3. The phi accrual failure detector replaces binary timeout detection with a continuous suspicion level based on statistical modelling of heartbeat arrival patterns — it adapts automatically to network conditions, becoming more lenient during periods of congestion and more sensitive during periods of stability
  4. Gossip protocols — particularly SWIM — scale failure detection to large clusters without O(N²) message overhead, using indirect probing to distinguish one-directional link failures from genuine node failures
  5. Failure detection tuning directly determines consensus system performance — the Raft election timeout and heartbeat interval ratio determines how many missed heartbeats trigger an election, and getting this ratio wrong causes unnecessary leader elections that consume availability budget
  6. Network partitions cause mutual false suspicion — failure detection must be combined with quorum requirements, fencing tokens, and odd cluster sizes to prevent partitions from producing split-brain scenarios
  7. Gray failures — nodes that respond to health checks but produce incorrect application results — are invisible to all heartbeat-based failure detectors and require application-level correctness monitoring

Frequently Asked Questions (FAQ)

What is a failure detector in distributed systems?

A failure detector is a mechanism that monitors nodes and produces suspicions about whether they have failed. It outputs “suspect” or “alive” for each monitored node based on heartbeats, timeouts, or statistical models of communication patterns. Failure detectors do not guarantee correctness — they provide probabilistic hints that higher-level protocols (Raft leader election, cluster membership management, replica promotion) use to trigger recovery actions. The two key properties are completeness (all actual failures are eventually detected) and accuracy (healthy nodes are not falsely suspected), which are in tension in any asynchronous network.

What is the phi accrual failure detector?

The phi accrual failure detector, introduced by Hayashibara et al. in 2004 and used by Cassandra and Akka Cluster, replaces binary timeout-based failure detection with a continuous suspicion level called phi (φ). Rather than declaring a node failed when a fixed timeout expires, it calculates how statistically surprising the absence of a heartbeat is given the historical heartbeat arrival pattern. A phi value below 1 indicates the node is very likely alive. A phi value of 8 or above indicates the delay is so improbable under normal conditions that the node is almost certainly failed. The adaptive threshold allows the detector to automatically become more lenient during periods of network congestion — the opposite behaviour of fixed timeouts.

What is the SWIM protocol?

SWIM (Scalable Weakly-Consistent Infection-style Process Group Membership) is a gossip-based failure detection protocol that scales to large clusters without O(N²) message overhead. Instead of every node monitoring every other node directly, each node periodically probes a random subset of nodes and gossips failure suspicions through the cluster. SWIM’s key innovation is indirect probing: before suspecting a node has failed, the detecting node asks other nodes to try contacting the suspect. This distinguishes one-directional link failures (the direct link is broken but the node is reachable through others) from genuine node failures. Consul, HashiCorp Serf, and many Kubernetes components use SWIM-based gossip for cluster membership.

How does failure detection interact with Raft leader election?

In Raft, follower nodes use a randomised election timeout as their failure detector. If the timeout expires without receiving a heartbeat from the leader, the follower assumes the leader has failed and starts an election. The critical tuning relationship is the ratio between the leader’s heartbeat interval and the follower’s election timeout — Raft requires this ratio to be at least 10:1 (heartbeat interval ten times smaller than election timeout) to prevent normal network variance from triggering false elections. etcd’s defaults are 100ms heartbeat interval and 1000ms election timeout. Cross-region deployments must increase both by approximately the cross-region network latency to avoid constant unnecessary elections.

Why do Raft clusters use odd numbers of nodes?

Raft requires a majority of nodes (quorum) to elect a leader and commit writes. In a cluster with an even number of nodes, a 50-50 network partition means neither side has a majority — neither side can elect a leader, and the system becomes completely unavailable for writes. With an odd number of nodes, any partition produces an unequal split: a 3-2 split in a 5-node cluster means the larger group has quorum (3 of 5) and can elect a leader, while the smaller group cannot. The system degrades gracefully rather than becoming completely unavailable. Three-node clusters tolerate one failure. Five-node clusters tolerate two failures. Adding a fourth or sixth node provides no additional fault tolerance over three or five nodes.

Can failure detectors detect gray failures?

No. Heartbeat-based failure detectors, phi accrual detectors, and gossip protocols all detect failures that manifest as absence or slowness of communication — crash-stop, crash-recovery, omission, and timing failures. They cannot detect gray failures, where a node responds correctly to heartbeats and health checks but produces incorrect results for application requests. A database replica that returns wrong query results due to a subtle corruption bug will pass all heartbeat-based detection while silently serving incorrect data. Gray failure detection requires application-level monitoring — synthetic transactions that exercise actual functionality, anomaly detection on error rates and latency distributions, and end-to-end correctness checks — which is covered in Post 4.8.

Continue the Series

Series home: Distributed Systems — Concepts, Design & Real-World Engineering

Part 4 — Fault Tolerance & High Availability Overview

Previous: ← 4.3 — Redundancy Patterns in Distributed Systems

Next: 4.5 — Recovery and Self-Healing Systems →

Related posts from earlier in the series:

Discover more from Rahul Suryawanshi

Subscribe now to keep reading and get access to the full archive.

Continue reading