Spreading state through gossip

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

In a gossip protocol each node periodically picks a few random peers and exchanges state with them. Information spreads like an epidemic, reaching all N nodes in about log N rounds.
It needs no coordinator, tolerates churn and lost messages, and gives every node a roughly constant load per round regardless of cluster size.
The price is eventual consistency: no node knows exactly when everyone has heard an update, and convergence time is probabilistic.
Typical uses are cluster membership and failure detection (Cassandra, Consul, Serf), spreading metadata such as token ownership or load, and anti-entropy repair of replicas.

How it works

The basic round

Every T seconds (often 1 s), a node picks k random peers (the fanout, often 1 to 3) and sends them a message. There are three styles. Push sends what I know. Pull asks what you know. Push-pull does both in one exchange and converges fastest, because push is fast while few nodes know and pull is fast while few do not.

With fanout 1 and push-pull, an update reaches 1,000 nodes in roughly 10 to 15 rounds. Doubling the cluster adds about one round. That logarithmic behaviour is why gossip scales to thousands of nodes.

Rumour-mongering versus anti-entropy

Rumour-mongering spreads new updates only: a node gossips a fresh item for a limited number of rounds, then stops. It is cheap but can leave a few nodes uninformed. Anti-entropy periodically compares full state between pairs and repairs differences, often using digests or Merkle trees so only the differing parts are sent. Production systems run both: rumours for speed, anti-entropy as the backstop. Van Renesse and colleagues' Scuttlebutt scheme exchanges per-node version digests first, so each side sends only entries newer than the other has seen (van Renesse et al.).

Membership with heartbeats

Each node keeps a table of (node, heartbeat counter, local time last increased). It increments its own counter each round and gossips the table. On receipt, a node keeps the higher counter per entry and records when it last saw it increase. If a peer's counter has not increased for T_fail (say 10 s), the peer is suspected, and after a further T_cleanup its entry is removed. Comparing counters, never remote timestamps, keeps this free of clock-sync assumptions.

Amazon's Dynamo found it useful to split membership in two. Joining or permanently removing a node is an explicit admin action written to persistent storage, and gossip only spreads that history, one random peer per second; temporary failures are detected locally by whoever fails to reach a node while forwarding requests. Early designs kept a gossiped global view of failures, but the explicit join and leave made it unnecessary, and seed nodes known to everyone stop the ring from splitting into groups that never hear of each other (Dynamo paper).

SWIM: separating detection from dissemination

Full-table heartbeat gossip sends O(N) data per message, which grows heavy at thousands of nodes. SWIM fixes this (SWIM paper). Each round a node pings one random member. If no ack arrives in time, it asks k other members to ping the target on its behalf (indirect probe), which filters out a single bad link. If those fail, the target is marked suspect, not dead, and the suspicion is gossiped. The suspect can refute it by gossiping a higher incarnation number. Membership changes ride piggybacked on the ping and ack messages, so dissemination costs no extra packets. HashiCorp's memberlist adds Lifeguard, which lengthens timeouts when the local node itself seems slow; in HashiCorp's experiments the full set of changes cut false positives by 50 to 100 times (Lifeguard paper).

Down the stack

Layer 1The contract

Gossip promises eventual, probabilistic delivery: with high probability every live node learns an update within O(log N) rounds, and per-node load stays roughly constant as the cluster grows. It promises nothing about ordering between updates, nothing about when a particular node hears, and nothing about agreement: two nodes can briefly disagree about who is alive. Failure detection is a trade between detection time and false-positive rate, never a guarantee. Anything built on top must tolerate stale and conflicting views, which is why gossiped state is usually versioned so that "highest version wins" merges are safe in any order.

Layer 2The mechanism

HashiCorp's memberlist, used by Consul and Serf, implements SWIM with Lifeguard. Its default LAN profile probes one member every second with a 500 ms probe timeout, asks 3 other members for an indirect probe on failure, and gossips queued broadcasts to 3 random members every 200 ms (memberlist config). Each broadcast is retransmitted 4 times the ceiling of log10(N+1), 16 times in a 2,000-node cluster, so it reaches everyone with high probability and then drops out of the queue. Message types include ping, indirect-ping, ack, suspect, alive and dead, encoded with msgpack and packed several to a datagram as a compound message. Every 30 s a node also does a full-state push-pull with a random peer over TCP as anti-entropy. Lifeguard keeps a local health score, raised when this node misses its own acks, and stretches its probe timeouts by that score (up to 8 times by default). The suspicion timeout has a floor of 4 × log10(N) probe intervals and starts at six times that floor, then shrinks toward the floor as independent members confirm the suspicion; two confirmations are expected (memberlist state.go).

Cassandra uses a different design. Each second a node gossips with a random live peer and sometimes with an unreachable node or a seed, using a three-message exchange (GossipDigestSyn, GossipDigestAck, GossipDigestAck2). Each endpoint's state carries a generation (the node's start time, so a restart outranks its old self) and a version that increments with every local change. Liveness uses the phi accrual detector: instead of a fixed timeout it estimates how unlikely the current silence is given recent heartbeat inter-arrival times, and convicts above a threshold of 8 by default (cassandra.yaml).

Layer 3The machine

memberlist keeps UDP payloads to about 1,400 bytes so a datagram fits in a 1,500-byte Ethernet MTU without IP fragmentation, since losing one fragment loses the whole datagram. A node therefore sends only a handful of small packets per second regardless of cluster size, a few kilobytes per second, while push-pull state is O(N) and goes over TCP. UDP has no retransmission, so the protocol's redundancy, not the kernel's, provides reliability: a dropped ping is covered by indirect probes through different network paths.

Most false positives come from the observer, not the network. A node starved of CPU by a noisy neighbour, a long GC pause, or a full socket receive buffer processes acks late and accuses healthy peers. Lifeguard's measurements showed large reductions in false positives by detecting that local slowness. Firewalls that allow TCP but drop UDP produce a classic failure: push-pull succeeds, probes fail, and nodes flap.

Why it's built this way

Any all-to-all scheme costs O(N²) messages, so each node talks to a constant number of random peers and epidemic spread gives O(log N) delivery.
Random peers and lossy links mean any single message can vanish, so updates are retransmitted several times and periodic anti-entropy repairs whatever slipped through.
A missed ping cannot distinguish a dead node from a bad link or a slow observer, so SWIM adds indirect probes, suspicion with refutation, and Lifeguard's self-awareness.
Fragmented UDP is fragile and TCP connections to every peer are costly, so frequent small messages fit one datagram and the rare full sync uses TCP.

Diagram

sequenceDiagram
    participant A as Node A
    participant B as Node B
    participant C as Node C
    participant D as Node D
    A->>B: ping
    Note over A,B: no ack within timeout
    A->>C: ping-req for B
    A->>D: ping-req for B
    C->>B: ping
    D->>B: ping
    Note over C,D: no ack from B
    C-->>A: no response
    A->>C: gossip B suspect, incarnation 4
    B->>A: refute, B alive, incarnation 5

Worked example

A 2,000-node Consul LAN pool with gossip interval 200 ms, fanout 3, and messages of about 1 KB with piggybacked updates.

Network load per node: 3 messages × 5 per second × 1 KB is about 15 KB/s each way. Across the cluster that is 30 MB/s of gossip, spread evenly, with no hotspot.
Spread time: log base 4 of 2,000 is about 5.5. With losses and overlap, expect an update to reach every node in about 8 to 10 rounds, roughly 2 s.
Failure detection: with every node probing one member per second, a crashed node is usually probed within a second or so, and after the 500 ms probe timeout and failed indirect probes it becomes suspect. The suspicion floor is 4 × log10(2,000) × 1 s, about 13 s, and the timer starts near 79 s, but a real crash is quickly confirmed by other probers, so the node is declared dead cluster-wide in roughly 15 s. That deliberate slowness is what gives a merely paused node time to refute.

Compare full-table heartbeat gossip: each message carries 2,000 entries of about 30 bytes, or 60 KB, and at 3 per second per node that is 180 KB/s per node and 360 MB/s cluster-wide. That difference is why large clusters use SWIM-style designs with piggybacked deltas.

Cassandra uses gossip every second with up to 3 peers for endpoint state such as load, schema version, and token ownership, plus a phi-accrual failure detector that outputs a suspicion level rather than a yes or no.

In the wild

Amazon S3, 2008: one flipped bit spread by gossip. On 20 July, error rates climbed in every S3 data centre at 8:40am PDT. S3 servers gossiped system state before handling each request, and a handful of messages had a single corrupted bit that left them readable but wrong. Servers ended up spending almost all their time gossiping or failing mid-gossip; the team had to stop all server-to-server traffic, clear state and restart, and US requests were back to normal only at 4:58pm. Afterwards S3 reduced gossip about failed servers, added gossip-rate alarms and began adding checksums on state messages (AWS post-mortem, archived).
HashiCorp, 2017: false positives from slow observers. HashiCorp found that its memberlist-based tools declared healthy members failed when a node was short of CPU or the network delayed or lost packets, which moved traffic away from healthy nodes and triggered needless rebalancing. Lifeguard's self-awareness, "dogpile" suspicion timeouts and direct notification of suspects cut false positives by more than 50 times without slowing real detection, and memberlist's defaults were retuned to detect failures 20% faster with 20 times fewer false positives (HashiCorp).
Amazon Dynamo, 2007: keeping permanent membership out of gossip's hands. Dynamo's authors note that outages are usually transient and that human error can start nodes by accident, so ring joins and removals are explicit admin commands, persisted and then spread by gossip each second. Seed nodes prevent logical partitions of the ring, and an early gossiped global failure view was dropped as unnecessary (Dynamo paper).

Trade-offs

Option	Strengths	Weaknesses	Choose when
Push-pull gossip	Fast convergence, simple	Probabilistic delivery time	General metadata spread
Heartbeat table gossip	Easy to implement	O(N) message size	Clusters under a few hundred nodes
SWIM with suspicion	Constant message size, fewer false positives	More states and timers	Large or churny membership
Central registry (etcd, ZooKeeper)	Strong consistency, exact membership	Coordinator load and availability	Membership must be exact, such as locks
Anti-entropy with Merkle trees	Repairs any divergence, bandwidth-efficient	CPU cost to build trees	Replica repair in Dynamo-style stores

Pitfalls in production

Asymmetric network faults make one bad node accuse healthy ones. Use indirect probes, suspicion with refutation, and Lifeguard-style local health awareness.
Overloaded nodes miss acks under CPU starvation and flap between alive and dead. Run gossip on a dedicated thread and alert on flap rate.
Mixed protocol versions during rolling upgrades can poison state. Version messages and ignore unknown fields.
Gossip pools that span WAN links suffer from high RTT and timeouts tuned for LAN. Use separate LAN and WAN pools, as Consul does (Consul docs).
Dead nodes that come back with old state can resurrect deleted entries. Use tombstones with expiry and incarnation numbers.

Leadership lens

Choose gossip when you need scalable, coordinator-free awareness and can tolerate seconds of staleness. Choose a consensus store when decisions must be exact.
Ask for numbers in review: cluster size, interval, fanout, message size, expected detection time, and false-positive rate.
Debugging is hard because state is everywhere. Insist on tooling that shows each node's view and on metrics for convergence time.
Prefer a proven library such as memberlist over a custom implementation; the edge cases live in timers and refutation.

Check yourself

Why does push-pull converge faster than push alone?
Show answer
Late in the spread most nodes already know the update, so pushes are wasted, while uninformed nodes pulling from informed ones still hit quickly.
Why does SWIM mark a node suspect instead of dead immediately?
Show answer
A missed ping can come from a slow link or a busy prober. Suspicion gives the node time to refute with a higher incarnation, cutting false removals.
Why compare heartbeat counters rather than remote timestamps?
Show answer
Counters need no clock synchronisation; each node measures staleness with its own local clock when a counter last increased.
What happens to gossip load per node as the cluster grows tenfold with SWIM?
Show answer
Message count and size per node stay roughly constant; only convergence and detection time grow, logarithmically.

Sources and further study

Primary

DeCandia et al., Dynamo (SOSP 2007): gossip-based membership, seeds and anti-entropy in a production store.
Hayashibara et al., The phi accrual failure detector: the detector Cassandra layers on top of gossip.

Systems docs

hashicorp/memberlist config.go: every LAN default with a comment explaining it.
Cassandra: cassandra.yaml reference: seeds, phi_convict_threshold and other gossip-related settings.
HashiCorp: Making gossip more robust with Lifeguard: the production motivation and measured gains.

Books

Database Internals, Alex Petrov, chapter 9 "Failure Detection" (gossip and failure detection) and chapter 12 "Anti-Entropy and Dissemination" (read repair, hinted handoff, Merkle trees).
Designing Data-Intensive Applications (1st edition), Martin Kleppmann, chapter 5 "Replication": leaderless replication, read repair and anti-entropy.

Other curricula

MIT 6.5840 Distributed Systems: teaches membership and fault tolerance through Raft and ZooKeeper, the exact-membership alternative to gossip.
donnemartin/system-design-primer: does not cover gossip; membership appears only as heartbeats between an active and a passive server.

Watch

Making Gossip More Robust with Lifeguard (HashiCorp): how SWIM false positives were reduced in memberlist.
Distributed Systems 4.3: Broadcast algorithms (Martin Kleppmann): gossip as a reliable broadcast technique, with its guarantees.

Free resources

SWIM paper: the original scalable membership protocol with suspicion and piggybacking.
Lifeguard (arXiv): HashiCorp's measured improvements to SWIM's false-positive rate.
Efficient Reconciliation and Flow Control for Anti-Entropy Protocols: van Renesse et al. on anti-entropy and the Scuttlebutt digest scheme.
Consul gossip protocol: LAN and WAN pools in a production system.
Gossip Dissemination (martinfowler.com): the pattern with code and convergence reasoning.

Open in the interactive app: practice, quiz, mock interview →