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