What you'll learn: By the end of this lesson you will be able to explain how gossip spreads cluster state without a coordinator, describe SWIM's probe, indirect probe and suspicion steps, compute and read a phi value from heartbeat timing, name the Cassandra and Consul settings that tune detection, and say why a failure detector can be tuned but never made perfect.
In an office with no public-address system, news travels by coffee-break chat: each person who knows tells two others, and by lunch the floor knows. Before announcing that a colleague has left, a careful person asks a couple of others to check too. A cluster needs the same two things: a way to spread news and a way to decide a peer is gone.
This lesson builds on Fallacies of Distributed Computing.
Verified against the SWIM paper, the phi accrual paper, Apache Cassandra 5.0 documentation and Consul documentation, read on 2026-11-08. The phi example ran on Python 3.14.2.
The core idea
Gossip is repeated random pairwise exchange of state; a failure detector is a separate component that decides, from missing replies, that a peer is down. The SWIM paper (Das, Gupta and Motivala) argues that all-to-all heartbeating fuses the two jobs, and that this is why its network load grows quadratically with group size or its detection turns slow or error-prone. SWIM separates them: members are monitored by periodic randomized probing, and membership changes ride on the probe messages.
Three illustrations: a minimal example (a phi calculation), a realistic example (a ShopStream cache cluster) and a failure example (a healthy but stalled node declared dead).
How gossip spreads state
In SWIM's analysis the spread is epidemic: an update piggybacked on pings and acks reaches the whole group in a number of protocol periods that grows logarithmically with group size, each update being piggybacked a bounded number of times. The authors note this is resilient to message loss, and that membership is deliberately weakly consistent: lists at different members need not agree at the same instant.
Cassandra's documentation gives a concrete schedule. Every second a node updates its own heartbeat state, exchanges its view of the cluster with one random peer, probabilistically tries an unreachable node, and gossips with a seed node if it did not in the random step. State carries (generation, version) logical clocks so stale information is ignored; see Logical and Vector Clocks. Seed nodes become gossip hotspots. In Consul's LAN pool (Serf, based on SWIM), gossip_nodes defaults to 3 peers per gossip_interval of 200 ms and retransmit_mult to 4, scaled with cluster size.
Failure detection with SWIM
SWIM has a protocol period T and a count k of indirect probers. Each period a member pings a random peer. With no ack before a timeout shorter than the period, it sends ping-req to k others, which ping the target and relay any ack. Only if nothing returns does it suspect the target. The paper says the period must be at least three times the round-trip estimate, and the indirect path stops congestion on one link from condemning a live peer.
Figure 1. A probe with indirect help. How to read this: the direct ping fails, so A recruits k others. One ack by any path clears C for this period. Updates ride on these messages instead of needing extra ones.
Message size is bounded and independent of group size, and the expected time to first detection does not depend on group size (the paper's figure labels it e/(e-1) periods). Round-robin target choice from a shuffled list bounds the worst case to two times the group size in periods.
Suspicion and incarnation numbers
One missed probe may be a slow process. SWIM marks the peer suspected and gossips that. If it answers, it is alive again. When a suspicion timeout expires it is declared faulty, a message that overrides the others.
Figure 2. The membership states. How to read this: the middle state buffers false positives. A member refutes a suspicion about itself with an Alive message and an incarnation number only it may raise, which orders old rumours against new.
The paper says suspicion reduces but does not eliminate false positives, and strong completeness (every crashed member is eventually detected by every correct one) still holds. A detector over an asynchronous network cannot be both strongly complete and never wrong, so detectors keep completeness and tune accuracy. Consul notes that Serf assumes the local node is healthy: if it is short of CPU or network, health checks can raise false alarms, which its Lifeguard extension addresses. Its probe_interval (default 1 s), probe_timeout (500 ms, which should be at least the 99th-percentile round-trip time) and suspicion_mult (4) set the same trade-offs; the WAN pool defaults are 5 s, 3 s and 6.
Phi accrual: a suspicion level, not a yes or no
A fixed timeout forces one trade-off on every user. Hayashibara and colleagues propose an accrual failure detector: it outputs a suspicion value on a continuous scale and each application picks its threshold. The phi detector keeps a sliding window of heartbeat arrival times, assumes they follow a normal distribution, and computes phi = -log10(P_later(t_now - T_last)), where P_later(x) is the probability that a heartbeat arrives more than x late. Suspecting at phi = 1 means about a 10 percent chance of being wrong, phi = 2 about 1 percent, phi = 3 about 0.1 percent.
Minimal example (illustrative: heartbeats about every 1,000 ms, standard deviation 100 ms):
from math import erfc, log10, sqrt
mean, sd = 1000, 100 # ms, illustrative
def phi(t): return -log10(0.5 * erfc((t - mean) / (sd * sqrt(2))))
for t in (1000, 1100, 1200, 1300, 1500, 1600): print(t, round(phi(t), 2))1000 0.3
1100 0.8
1200 1.64
1300 2.87
1500 6.54
1600 9.01Phi first reaches 8 after 1,562 ms of silence (Cassandra's default threshold, below). Cassandra's documentation says every node runs a variant of the phi detector and decides alone whether peers are up; this lesson uses the paper's normal model, not Cassandra's code. phi_convict_threshold defaults to 8 ("most users should never need to adjust this"). Up and down are local decisions that are not gossiped; heartbeats are. A convicted node stops receiving reads, writes typically go to hints, and a node leaves gossip state only by an operator's instruction.
Trade-offs
| Approach | Strength | Cost |
|---|---|---|
| All-to-all heartbeats | Simple, fast | Load grows quadratically with group size |
| SWIM: random probes, piggybacked gossip | Constant load, bounded messages | Weakly consistent views; suspicion needs tuning |
| Accrual detector (phi) | Adapts to the network, per-use thresholds | Window and distribution assumptions |
| Consensus-based membership | One agreed view | Coordination; no answer without a majority |
Figure 3. Choosing the membership style. How to read this: the question is about the action taken on the view. A cache read can retry; a payment or a leader decision cannot.
In practice: a ShopStream cache cluster
This is the realistic example, an educational scenario on ShopStream. Nothing in it describes a real company; the cluster size and timings are illustrative.
This is a realistic scenario, not a case history.
The situation
ShopStream's browse path uses 30 cache nodes. Clients need a view of which are alive without calling a central service on every request, and a slightly stale view only costs a cache miss that falls back to the database.
Starting architecture
Figure 4. The cluster as designed. How to read this: there is no coordinator. Each node gossips with random peers and runs its own detector; the seed is where new nodes start and tends to receive extra gossip.
Options considered
| Option | Behaviour | Risk |
|---|---|---|
| A. Central registry | One view, an extra dependency on every read | Registry outage hurts all reads |
| B. SWIM-style gossip, fixed suspicion timeout | Decentralised, constant load | One timeout suits one network state |
| C. Gossip with an accrual detector | Adapts to jitter | A wrong threshold flaps nodes |
The decision
Option C with the detector's default threshold, revisited after observing the cluster. Weak consistency is acceptable because a miss falls back to the database. It would not be acceptable for stock or payments, which need an agreed view and use consensus.
Rollout and verification
In staging, stop one node, pause another and delay a third one's network, and record how long peers take to mark each down and up again. Metrics: nodes marked down per hour, time to detection, and flapping.
The 2 a.m. failure
Nodes are marked down and up in rotation. A long pause on one overloaded node made peers convict it, its reads moved to the others, their load rose, and they began missing heartbeats too. Check which peers convict which nodes and whether the timing matches a deploy or a pause. Mitigate by cutting load and fixing the pause, not by restarting the cluster; raise the threshold only as a measured, temporary step.
Architect's notes
- Tune "spread" and "decide" separately, from measured round-trip times.
- Suspect before declaring death: plan for the slow node, not only the dead one.
- Use gossip for views that may be stale, consensus for views that may not.
Common mistakes
- Treating a missed heartbeat as proof of a crash. Slow and dead look the same.
- Copying one timeout to every environment.
- Raising the threshold to silence flapping without finding the pause behind it.
- Expecting all nodes to share one view at one instant.
Key takeaways
- Gossip spreads updates in rounds that grow slowly with cluster size.
- SWIM separates detection from dissemination, probes indirectly and suspects before declaring.
- Phi accrual outputs a suspicion level and each application picks a threshold.
- No detector is both always accurate and complete on an asynchronous network.
Practice exercises
Exercise 1 (30 min). Change the mean and standard deviation in the phi snippet and find when phi crosses 8.
Exercise 2 (45 min). Using Consul's defaults for probe_interval, probe_timeout and suspicion_mult, describe what a missed probe causes first and what follows.
Related reading
- Service Discovery: heartbeat-based registries.
- Logical and Vector Clocks: clocks behind versioned state.
- CRDTs and Conflict Resolution: state that merges when gossiped.
- Consensus and Leader Election: the consistent alternative.
Official documentation
- Das, Gupta and Motivala, SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol (Cornell).
- Hayashibara, Defago, Yared and Katayama, The phi Accrual Failure Detector (JAIST research report IS-RR-2004-010, 2004).
- Apache Cassandra 5.0: Dynamo architecture, gossip and failure detection and cassandra.yaml.
- HashiCorp Consul: Gossip and gossip parameters.