---
title: Failure Detection
url: https://doc.liz6.com/en/distributed-systems/05-members-and-discovery/01-failure-detection
locale: en
area: distributed-systems
tags:
- distributed-systems
- members-and-discovery
date: 2026-06-30
modified: 2026-07-16
description: In an asynchronous network, if a node does not reply to a message, is it truly dead or just slow? The φ-accrual failure detector does not answer "yes or no," but instead outputs a "probability that it is dead," allowing upper-layer protocols to make their own decisions based on business sensitivity. SWIM combines this probability calculation with gossip-based membership propagation.
---

# Failure Detection

> In an asynchronous network, if a node does not reply to a message, is it truly dead or just slow? The φ-accrual failure detector does not answer "yes or no," but instead outputs a "probability that it is dead," allowing upper-layer protocols to make their own decisions based on business sensitivity. SWIM combines this probability calculation with gossip-based membership propagation.

## Why Failure Detection is Hard

In asynchronous networks (without synchronized clocks or upper bounds on message delays), it is **impossible to perfectly distinguish between a "node crash" and "slow network."** Any timeout-based detection mechanism is prone to false positives. Failure detectors must provide the "most reasonable" suspicion under such uncertainty.

## Simple Heartbeat

```
Every T seconds: Node A sends a heartbeat → to node B
  If B does not receive a response within timeout (e.g., 3T) → mark A as dead
```

Problem: Fixed timeouts are too rigid. Network jitter leads to false positives. Increasing the timeout increases the detection delay for actual crashes.

## φ-accrual Failure Detector

Instead of outputting a binary alive/dead status, it outputs **φ: suspicion level**—how unlikely it is that the node is currently alive. The upper-layer application can decide "what φ value triggers a failover."

### Principle

Record the distribution of historical heartbeat arrival intervals (mean μ, variance σ²). For each delayed arrival (current time - last heartbeat arrival time = t), calculate φ:

```
φ = -log10(P(arrival interval > t | distribution))
```

If heartbeats usually arrive within 100ms, but this time it took 500ms—that is highly unlikely → φ is large. If it took 150ms—that might just be jitter → φ is small.

Advantages:
- Adaptive: Makes decisions based on actual network conditions (not fixed "3 timeouts")
- Configurable: Different services can use different φ thresholds. Low-latency critical services → failover at φ=5. Background services → failover at φ=10

Applications: Akka (JVM actor framework), Cassandra (PhiConvictAdaptive failure detector).

## SWIM (Scalable Weakly-consistent Infection-style Membership)

The most widely used failure detection and membership discovery protocol (used under the hood by Consul, Serf, Tailscale).

### Protocol

```
Each member runs independently:

Every T₁ seconds (e.g., 1s):
  1. Randomly select a member P
  2. Send PING → P
  3. If P does not reply with ACK within T₂ (e.g., 500ms):
     → indirect ping: Randomly select K members (e.g., 3), ask them to ping P
     → If all K members receive ACK → P is alive
     → If none of the K members receive ACK → P is suspected

  4. Start gossip:
     - If P is suspected: Select M random members, send gossip message: P is suspected
     - Gossip receiver: Stores this information. If it successfully pings P itself → refutes suspicion (sends alive message)
```

### SWIM vs Heartbeat

- Heartbeat: O(N) messages per second (each member sends to all other members)
- SWIM: O(1) ping per member per period + gossip = extremely low bandwidth, supports thousands of nodes
- SWIM's indirect ping significantly reduces false positives: Direct member-to-member connections may drop packets due to local network faults, but if multiple other nodes can ping P → it is not dead

## Timeout Strategies

TCP connect timeouts, RPC deadlines, gossip suspicion timeouts—all address the same problem. Design principles:

1. **Set based on p99.9 latency**: Timeouts must be > p99.9 latency, otherwise the false positive rate is unacceptable
2. **Distinguish between timeout and deadline**: timeout = maximum wait time for network/RPC; deadline = final deadline for the entire operation (after multiple retries)
3. **Retry with exponential backoff + jitter**: Prevent thundering herd → all waiting clients retry simultaneously → taking down the just-recovered service
4. **Budget timeout**: Allocate the total timeout for the entire request chain (A→B→C→D) across its components → fail fast without dragging down the entire chain

## References

- **Paper**: "The φ Accrual Failure Detector" (Hayashibara et al, 2004)
- **Paper**: "SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol" (Das et al, 2002)
- **Serf**: serf.io (HashiCorp, SWIM implementation)

*Keywords: heartbeat, φ-accrual, SWIM, indirect ping, gossip, failure detector, membership protocol*