Gossip: Push-Pull Anti-Entropy & SWIM Failure Detection

The problem

A cluster of hundreds or thousands of nodes needs shared, slowly changing knowledge: who is a member, who is alive, which node owns which token range, the schema version, feature flags. A central registry becomes a bottleneck and a single point of failure. Broadcasting every change to everyone costs O(N) per sender and falls apart under loss. Gossip has each node talk to a few random peers per round. An update then reaches all N nodes in O(log N) rounds, with O(1) work per node per round, and it tolerates lost messages and crashed nodes without any extra machinery.

The second half of the problem is failure detection. Heartbeating everyone to everyone costs O(N²) messages. SWIM gets constant load per member and O(1) expected detection time, and rides the gossip channel to spread its verdicts.

Where it shows up: Cassandra/ScyllaDB (ring state, schema, phi-accrual detector), HashiCorp memberlist (Consul, Nomad, Serf), Amazon Dynamo (membership), Redis Cluster (cluster bus PFAIL/FAIL), Akka Cluster, Uber Ringpop, and Bitcoin/Ethereum transaction relay.

Design

gossip.js is one simulation with synchronous rounds, a lossy Network, and a seeded mulberry32 PRNG, so every run is reproducible.

Part 1: anti-entropy of versioned state (GossipCluster)

• Each entry is {value, version, writer}. version comes from the writer's Lamport clock: set() increments it, and merge() does clock = max(clock, received). A write made after seeing version 41 therefore gets version 42 or more, and supersedes what the writer saw.
• Merge = last-writer-wins on (version, writer). It is a total order, so merge is commutative, associative and idempotent (a state-based CRDT). Replicas converge whatever the order, duplication or loss of messages. Ties (concurrent writes with equal versions) are broken by writer id. That is deterministic, and it deliberately loses one of the writes.
• Push-pull exchange uses the same three steps as Cassandra's gossip: 1. SYN: p sends a digest (key, version, writer), with no values. 2. ACK: q replies with entries newer than p's, and the keys where p is newer. 3. ACK2: p sends the requested entries. Peers that are already in sync exchange only digests. Modes push (send full state) and pull (digest, then deltas) exist for comparison.
• Round model: in each round every live node contacts fanout random peers, and messages are built from start-of-round snapshots. A rumour therefore moves at most one hop per exchange per round, which is the model the O(log N) results assume.

Measured rounds to convergence (one update, fanout 1, no loss; node demo.js)

Push matches Pittel's log2 N + ln N + O(1). Push-pull is much faster, consistent with Karp et al.'s log3 N + O(log log N). At N = 256, fanout 3 takes 4.2 rounds instead of 7.6, and 30% message loss raises the count from 7.6 to 15.7 rounds but still converges.

Part 2: SWIM failure detector (SwimCluster)

Why SWIM instead of phi-accrual: phi-accrual (Cassandra, Akka) turns heartbeat inter-arrival statistics into a suspicion level, but it still needs heartbeats from every monitored peer. SWIM decouples detection from dissemination. It has constant per-member load, needs no per-peer timing history, and verifies failures through other members instead of trusting one lossy path. It is the protocol behind memberlist and Consul.

Each protocol period, every live member:

1. Probes the next target in a shuffled round-robin list. Round-robin bounds the time until a member is probed to 2N-1 periods; random choice gives an expected e/(e-1) ≈ 1.6 periods to first detection but no worst-case bound.
2. If the ping or its ack is lost, it sends a ping-req through k random helpers (default 3). Any helper's ack counts.
3. If everything fails, it marks the target SUSPECT (with the target's known incarnation) instead of DEAD.
4. A suspect that hears about its own suspicion refutes it: it increments its incarnation and spreads ALIVE(inc+1).
5. A suspicion that nobody refutes within suspicionRounds (default 2·⌈log2(N+1)⌉) becomes DEAD at that observer.

Precedence rules (the unit test covers each one): ALIVE(i) replaces SUSPECT/DEAD only if i > current; SUSPECT(i) replaces ALIVE(j) if i ≥ j; DEAD replaces anything that is not already DEAD with i ≥ current. Updates are piggybacked (up to 6 per message) on ping/ack/ping-req traffic, freshest first, and each one is sent 4·⌈log10(N+1)⌉ times, which is memberlist's retransmit rule.

False DEAD declarations about healthy members (32 nodes, 100 periods, 3 seeds):

Complexity

• Anti-entropy: O(fanout) exchanges per node per round. Digest size is O(keys), and deltas are O(changed keys). Spreading one update takes O(log N) rounds and O(N log N) messages in total.
• SWIM: an expected O(1) messages per member per period (1 ping, plus k·4 when a ping fails). First detection takes an expected ~1.6 periods. Full dissemination takes O(log N) periods after the suspicion timeout.
• Memory: O(keys) per node for the KV state, and O(N) per node for the membership table.

Failure modes & trade-offs

• Digest cost grows with state. Sending every key's version each round is fine for cluster metadata and wasteful for large data sets. Dynamo and Cassandra repair use Merkle trees for bulk data instead.
• LWW silently drops concurrent writes. For data where that matters, use version vectors or CRDTs with richer merges (OR-sets, counters).
• Lamport versions only work if clocks are persisted. A node that restarts at clock 0 writes versions that lose to its old ones. Cassandra pairs a generation (boot timestamp) with a per-boot version for exactly this reason.
• Suspicion timeout trade-off: a longer timeout means fewer false positives and slower detection of real crashes. Lifeguard adapts timeouts to a member's own health (its "local health multiplier").
• Piggyback capacity: under heavy churn the update queue outgrows the 6-updates-per-message budget, refutations arrive late, and false positives rise (the "ping only" column shows this feedback loop). memberlist limits updates by UDP packet size.
• Partitions: SWIM on each side will declare the other side dead. Gossip does not solve split brain. Pair it with consensus for anything that needs a single decision.

How production systems do it

• Cassandra: once a second, each node gossips with one random live peer, maybe one unreachable peer, and maybe a seed, using GossipDigestSyn / Ack / Ack2. Endpoint state is versioned by (generation, version). Failure detection is phi-accrual (phi_convict_threshold, default 8).
• HashiCorp memberlist (Consul, Nomad, Serf): SWIM + Lifeguard over UDP, with a 1 s probe interval, 3 indirect checks, suspicion multiplier 4 and retransmit multiplier 4. It also runs a periodic TCP push-pull full-state sync (30 s by default), which is the anti-entropy half of this build.
• Amazon Dynamo: gossip-based membership and token-map propagation, with seed nodes to prevent logical partitions, and Merkle-tree anti-entropy between replicas.
• Redis Cluster: nodes ping random peers over the cluster bus and mark unresponsive ones PFAIL (like SUSPECT). A node becomes FAIL only when a majority of masters report it.
• Akka Cluster: membership state gossiped with vector clocks, and a phi-accrual detector on each node's heartbeat.

Extension exercises

1. Add phi-accrual as an alternative detector (a sliding window of heartbeat intervals, phi = -log10(1 - CDF(Δt))) and compare detection time and false positives against SWIM on the same seeds.
2. Let GossipCluster choose peers from SwimCluster's live view, so dead nodes stop wasting fanout.
3. Replace full digests with a Merkle tree per node, and measure bytes exchanged against the number of keys when only 1% of the keys differ.
4. Swap LWW registers for an OR-set CRDT, and show that concurrent add/remove no longer loses an add.
5. Add Lifeguard's local health multiplier: a node that is missing acks itself stretches its own probe timeout and suspicion timeout. Measure false positives when one node is overloaded.