Gossip protocol

A gossip protocol spreads information through a cluster the way news spreads through a neighbourhood: every second or so, each node picks a few random peers and swaps what it knows. Nobody is in charge, each node’s load stays flat as the cluster grows, and an update reaches all N nodes in about log N rounds. Cassandra, Consul and Redis Cluster use it to track who is in the cluster, who looks dead and who owns what.

Picture it first: news in a housing society

A housing society has 1,000 flats and no notice board. The water supply will be off tomorrow from 10 to 2, so the secretary tells three neighbours on her evening walk. The society has one habit: every evening, anyone who knows some news mentions it to three random people they bump into.

Evening one, 4 flats know. Evening two, up to 16; evening five, about 600; by evening eight, virtually everyone. Nobody kept a list of who had been told, and if the secretary leaves for Pune the next morning, the news spreads anyway, like a WhatsApp forward.

Two details make it work. People repeat the latest version: if the timing changes to 11 to 3, the newer message wins wherever the two meet. And many conversations are wasted (“I know, I heard yesterday”), the price of nobody coordinating.

Map it back: flats are nodes, the evening walk is a gossip round, “three people” is the fanout, the news is a state update (a node joined, a node looks dead, a partition moved) and the timing change is a newer version. A notice board at the gate would be the central registry: accurate, but everyone must walk to it, and if it blows over nobody learns anything.

How a gossip round works

Every node runs the same small loop, with no leader and no shared schedule:

1. Wait one interval. Cassandra gossips once a second; HashiCorp’s memberlist library every 200 ms.
2. Pick k random peers from the local member list. k is the fanout: Cassandra talks to one random live node per round (sometimes also an unreachable node and a seed); memberlist gossips to 3.
3. Exchange state, or a compact digest of it, and get the peer’s view back.
4. Merge: for every entry, keep whichever copy has the higher version.

Three properties fall out. Work is constant per node: k messages per interval, whether the cluster has 50 nodes or 5,000. It is robust: a lost message or a crashed peer removes one path out of many. And it is eventually consistent: two nodes may disagree at any instant, but once updates stop, every view converges.

Systems gossip membership, liveness hints (heartbeat counters, “suspect” and “dead” verdicts), cluster metadata (which node owns which consistent hashing tokens, schema versions, load) and sometimes aggregates: if pairs of nodes keep averaging their two values, the total never changes and every node drifts towards the cluster-wide mean.

Why it takes only O(log N) rounds

Take N = 1,000 nodes, fanout k = 3 and one round a second, and assume every node that knows an update pushes it to 3 random peers each round.

Early rounds multiply. While almost nobody knows, nearly every push lands on someone new, so the count grows up to 4× per round. Expected counts: 1 → 4 → 16 → 62 → 221 → 598. Reaching most of the cluster takes about log₄ 1,000 ≈ 5 rounds.

Late rounds mop up. Once most nodes know, each of roughly 3N pushes misses a given straggler with probability 1 − 1/N, so it escapes a whole round with probability about (1 − 1/N)^3N ≈ e⁻³ ≈ 0.05. Each round cuts the stragglers about 20×: about 66 left after round 6, 4 after round 7, 0.2 after round 8, 0.01 after round 9.

The chance anyone is missed. When the expected number of stragglers is small, it roughly equals the chance that at least one exists. So after 8 rounds there is still about an 18% chance someone hasn’t heard; after 9, about 1%; after 10, about 0.05%. At one round a second, the whole cluster knows within 9–10 seconds. A quick simulation (100 runs) agrees: 8.2 rounds on average, never more than 10.

Scale barely matters. At N = 10,000 you need about 10 rounds: two more for 10× the nodes, because log₄ 10 ≈ 1.7. Each node still sends 3 messages a second and receives 3 on average; the cluster sends 3N, but no single node feels N.

Extra fanout has diminishing returns: one peer per round needs 17 rounds, two need 10 and three need 8, for 1, 2 and 3 messages per node per round. The other lever is the interval: gossiping every 200 ms instead of every second is 5× faster for 5× the packets, a trade memberlist makes on a LAN.

Push, pull and push-pull

The 1987 paper by Alan Demers and colleagues at Xerox PARC, “Epidemic Algorithms for Replicated Database Maintenance”, named the three ways two nodes can resolve a difference:

• Push: the caller sends its newer data to the partner. Helps only if the partner is behind.
• Pull: the caller asks the partner for anything newer. Helps only if the caller is behind.
• Push-pull: both directions in one exchange, so both end up current.

The difference shows up in the tail. Let p be the fraction of nodes still missing an update. With pull, a straggler stays behind only if the node it asks is also a straggler, so p falls to p² each round: 1% becomes 0.01%. With push, a straggler stays behind only if no informed node picks it, so p shrinks only by a factor of about e: 1% becomes 0.37%. Push-pull behaves like pull.

Push has one advantage: when nothing changes, it sends nothing, while pull keeps asking “anything new?”. A common split is push for fresh news and push-pull for periodic full syncs, such as Cassandra’s three-message exchange.

Rumour mongering and anti-entropy

Demers’ team was fixing a real outage. Xerox’s Clearinghouse name servers mailed every update to every site, then ran a nightly reconciliation that re-mailed corrected values; for a domain stored at 300 sites, that could add 90,000 mail messages a night and broke mail and name lookups across the company. Their fix produced the two styles every gossip system still uses.

Anti-entropy is the thorough one. Each site periodically picks a random partner and the two reconcile their entire databases. Sites never stop sharing, so every update eventually reaches everyone. With push and one partner per round it takes about log₂ n + ln n rounds: for 1,000 sites, about 10 + 7 = 17, matching the fanout-1 curve above. The cost is comparing whole databases.

Rumour mongering is the cheap one. Each site is susceptible (hasn’t heard), infective (holds a “hot rumour” and keeps sharing it) or removed (knows, but has stopped). A site loses interest after k calls to people who already knew (a counter) or with probability 1/k per call (a coin).

Rumours are cheap because they die out, and that is also their flaw: one can die before reaching everyone. The paper calls the fraction never reached the residue. For 1,000 sites using push and a counter:

For push, residue s and messages per site m follow roughly s = e^−m. Pull does far better: about 4 in a million at 6.1 messages per site with k = 3.

The standard answer is to use both: rumours spread news fast and cheaply, and infrequent anti-entropy catches whatever they missed. SWIM’s piggybacked updates plus memberlist’s periodic full sync follow this pattern, and so does Dynamo-style replication, where hinted handoff and read repair are the fast path and Merkle-tree repair is the safety net (quorums and leaderless replication).

Making anti-entropy cheap means not shipping what already matches. Exchange digests of versions and send only entries where the other side is behind, as Cassandra does every second, or compare Merkle trees, descending only where hashes differ. A Bloom filter is another compact summary of “what I already have”, at the price of occasional false positives.

Deletes need care: if a site simply drops an item, anti-entropy with a site that still has it brings it back. The paper’s fix is a death certificate, a timestamped deletion record that spreads like any update and is purged only after it has had time to reach everyone, the same idea as Cassandra’s tombstones.

Versioned state and safe merges

Gossip only works if merging is safe no matter how often, or in what order, the same information arrives. The usual design:

• Each node owns its own entries; others only relay them.
• Every change bumps a version number, and a heartbeat counter bumps it even when nothing else changes, which is how silence becomes visible.
• A generation number changes on restart, usually the start-up timestamp, so a rebooted node’s fresh version 1 beats its old version 900.
• Merge means keep the maximum (generation, version) per entry.

“Keep the maximum” is commutative, associative and idempotent: order and grouping don’t matter, and duplicates change nothing. That is why gossip can resend freely over unreliable UDP, and it is the property that makes CRDTs work (clocks, ordering and conflict resolution). The trap is gossiping operations: send “orders +1” and duplicates double-count. Gossip each node’s own running total instead (A: 41, B: 17), and anyone can add them up.

Cassandra is the textbook case. Each node keeps an endpoint state for every node it knows, a heartbeat plus application states such as status, tokens, schema version and load, versioned by (generation, version). A round is a three-message push-pull: SYN carries one digest per known node, ACK asks for what the receiver lacks and returns what the sender lacks, and ACK2 completes the swap.

Every second, each Cassandra node bumps its own heartbeat version and gossips with one random live node, sometimes an unreachable node, and a seed if its first pick wasn’t one. Two choices are worth copying. UP and DOWN are local opinions: each node runs its own phi accrual detector over the heartbeats it receives (heartbeats), and the verdict is never gossiped. And nothing is removed automatically: a node leaves gossip state only when an operator decommissions or replaces it, so a five-minute reboot never triggers a data reshuffle.

SWIM: membership and failure detection by gossip

All-to-all heartbeating costs O(N²) messages (heartbeats compares the topologies), and gossiping every node’s heartbeat counter makes every message grow with N. SWIM (Das, Gupta and Motivala, 2002) splits the job in two: a failure detector that probes one random peer per period, and a dissemination layer that piggybacks membership news on those probes.

In each protocol period (1 s in memberlist), member Mi:

1. Pings one member, Mj, and waits for an ack (memberlist waits 500 ms).
2. If none comes, sends ping-req(Mj) to k other members, who ping Mj and relay any ack. This separates “Mj is down” from “my path to Mj is bad”.
3. If still nothing by the end of the period, marks Mj suspect, not dead, and spreads that.
4. Mj, on hearing it, refutes with an alive message carrying a higher incarnation number. If no refutation arrives before the suspicion timeout, Mj is confirmed dead.

Incarnation numbers are SWIM’s versions, and only Mj can raise its own. Alive at a higher incarnation beats suspect at a lower one; suspect beats alive at the same incarnation; a confirmed death beats everything.

The guarantees are why SWIM caught on. The chance that nobody picks Mj in a period is about (1 − 1/N)^N ≈ 1/e, so a failure is first detected in about e/(e − 1) ≈ 1.6 periods on average, whatever N is. Each member sends and receives about two messages per period. Each update is piggybacked about λ·log N times, reaching everyone in O(log N) periods; in the prototype no message exceeded 135 bytes. Picking ping targets round-robin through a shuffled list bounds worst-case first detection at 2N − 1 periods.

Lifeguard: suspect yourself first

SWIM assumes the prober is healthy, but a node starved of CPU processes acks late and then accuses healthy peers. HashiCorp’s Lifeguard extensions (Dadgar, Phillips and Currey, 2017) make each node track its own local health:

• Local health aware probe: a counter rises on failed probes, on having to refute suspicion of itself, and on missing nacks (helpers send one when their indirect ping fails, proving the path to them works). Probe interval and timeout scale with the counter, up to 9×, so a struggling node slows down instead of accusing others.
• Local health aware suspicion: the suspicion timeout starts long and shrinks as independent suspicions arrive. A lone, possibly sick accuser waits; a chorus acts fast.
• Buddy system: whoever pings a suspect piggybacks the suspicion, so it can refute at once.

In their experiments this cut false positives 50–100× without slowing real detection; the paper reports Consul deployments with over 6,000 members in one group.

memberlist, Serf and Consul in numbers

memberlist, the Go library under Serf, Consul and Nomad, is SWIM plus Lifeguard plus a faster, separate gossip layer and a periodic full push/pull state sync over TCP, which helps partitions heal. Its LAN defaults:

The suspicion timeout grows with log N because in a bigger cluster the news takes longer to reach the suspect.

Consul runs two Serf pools: a LAN pool per datacentre (port 8301) that every agent joins, and a WAN pool (port 8302) linking datacentres. Its servers keep the service catalog in Raft, not gossip; see service discovery.

Gossip in production

Redis Cluster keeps a full mesh of TCP connections on its cluster bus. Each node pings a few random nodes every second, plus any node it hasn’t heard from in half of NODE_TIMEOUT, and every ping and pong carries a gossip section about a few random nodes. A node silent for NODE_TIMEOUT gets a local PFAIL (“possibly failing”) flag. Once a node collects PFAIL or FAIL reports about it from a majority of masters within 2 × NODE_TIMEOUT, it marks it FAIL and broadcasts that, and the failed master’s replicas can stand for election. The spec’s arithmetic: with 100 nodes and a 60 s timeout, each node pings its 99 peers every 30 s, 3.3 pings a second, so 330 a second cluster-wide. More in Redis.

Going deeper: costs and failure modes

State size is the real scaling limit

Per-node load is constant only if messages stay small. Cassandra-style digests carry one entry per node; say about 25 bytes each (an estimate). At 1,000 nodes a digest is about 25 KB, and at one exchange per node per second the cluster moves 1,000 × 25 KB = 25 MB/s on digests alone. At 10,000 nodes each digest is 250 KB and the cluster moves 2.5 GB/s: 10× the nodes, 100× the traffic, back to O(N²). Dynamo’s authors said as much: gossiping the full routing table works for a couple of hundred nodes, not tens of thousands. The fixes: gossip deltas in small, size-capped packets (memberlist fills a 1,400-byte UDP buffer) and keep full syncs rare; shrink what each node must know (Dynamo cut its membership data by three orders of magnitude with fixed, equal-sized partitions); and go hierarchical, like Consul’s per-datacentre pools.

Partitions give you two truths

Gossip spreads opinions; it never decides. If a split cuts a 10-node cluster into 6 and 4, each side declares the other dead and carries on with its own view until the network heals and full syncs merge them. That is fine for “where should I route this read” and dangerous for “who is the leader”: gossip has no quorum, so both sides can act. Systems that must decide add a vote: Redis Cluster needs a majority of masters to mark FAIL and their votes to promote a replica, Consul keeps its catalog in Raft, and Cassandra never removes a node without an operator. See consensus and leader election and CAP and PACELC.

Seeds are bootstrap helpers, not leaders

A new node needs at least one address to join. In Cassandra, seeds differ from other nodes only in being allowed to bootstrap without seeing another seed, and in attracting extra gossip. Dynamo shows the trap: an admin tells node A to join the ring, then node B, and each believes it is a member without knowing the other, a logical partition. Seeds, which every node eventually reconciles with, prevent it, but only if seed lists overlap.

False suspicions and flapping

A GC pause longer than the suspicion window gets a healthy node declared dead; it refutes and rejoins, and anything wired to membership events runs twice. Worse, one slow node can accuse many healthy ones. The remedies are refutable suspicion, timeouts that grow with log N, Lifeguard and, in Cassandra, an adaptive phi detector with no automatic removal.

Security and tuning

A gossip port accepts messages from anyone who can reach it, and a forged “dead” verdict spreads like real news. Encrypt and authenticate gossip: memberlist supports AES keys with a keyring, and Consul recommends a dedicated gossip key, rotated periodically (encryption and key management).

Every tuning knob makes the same trade: a shorter interval or higher fanout spreads news faster for more packets, and a longer suspicion timeout means fewer false deaths but slower real detection.

Gossip versus the alternatives

How to choose:

• A 500-node Cassandra ring needs token ownership and rough liveness everywhere, and a few seconds of disagreement only reroutes some reads: gossip.
• A shard’s primary, a lock, the live config: two answers would corrupt data, so use Raft via ZooKeeper or etcd.
• Five workers and a coordinator: plain heartbeats; even all-to-all is only 5 × 4 = 20 messages a second.
• Service discovery across 2,000 VMs: both, as Consul does.
• No trusted servers at all: gossip is often the only option (peer-to-peer architecture).

Cheat sheet

How to say it in the interview

“For membership across these 800 cache nodes I’d use a SWIM-style gossip library like memberlist. Each node probes one random peer a second; with no ack it asks three others to probe for it, then marks the peer suspect rather than dead, so a GC pause can be refuted. Changes ride on the probes and reach everyone in O(log N) rounds, a few seconds here, while each node sends a handful of small packets a second. Views are eventually consistent, which is fine for routing; anything that needs a single answer, like a shard’s primary, goes through Raft in etcd.”

How long until every node hears about a change? About log₍ₖ₊₁₎ N rounds plus a short tail: with 1,000 nodes, fanout 3 and one round a second, about 9 seconds for 99% confidence. 10× the nodes adds about 2 rounds.

Why not heartbeat to a central server? Below a few hundred nodes that is often simpler. But the server is a single point of failure and a hot spot taking N messages per interval; gossip spreads the load and has nothing central to lose.

What happens during a network partition? Each side declares the other dead and carries on; when the network heals, full syncs merge the views. Gossip never picks a winner, so a leader or a lock needs a quorum-based protocol.

How does SWIM avoid declaring a slow node dead? Indirect probes rule out one bad link, suspicion lets the node refute with a higher incarnation number, and Lifeguard makes a struggling prober slow down instead of accusing others.

What stops gossip bandwidth exploding as the cluster grows? Small deltas piggybacked on probes, rare full syncs, less state per node, and hierarchical pools.

Where to go next

• Heartbeats: timeouts, phi accrual and why slow looks like dead.
• Service discovery: Consul’s Serf gossip plus a Raft catalog.
• Consensus and leader election: when nodes must agree, not just hear.
• Clocks, ordering and conflict resolution: version vectors and CRDTs.
• Quorums and leaderless replication: read repair, hinted handoff and Merkle trees.
• Cassandra and DynamoDB: gossip-based membership in production.
• Design a key-value store: gossip, consistent hashing and quorums together.
• Peer-to-peer architecture: systems with no servers at all.

References and further reading

1. Epidemic Algorithms for Replicated Database Maintenance (Demers et al., PODC 1987; Xerox PARC report CSL-89-1)bitsavers.trailing-edge.comDirect mail, anti-entropy and rumour mongering; push vs pull convergence; residue versus traffic tables for 1,000 sites; death certificates; the Clearinghouse incident.
2. SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol (Das, Gupta and Motivala, DSN 2002)cs.cornell.eduPing, ping-req and suspicion, incarnation numbers and override rules, piggybacked dissemination, round-robin probing and prototype measurements.
3. Lifeguard: Local Health Awareness for More Accurate Failure Detection (Dadgar, Phillips and Currey, 2017)arxiv.orgLocal health multiplier, nacks, dynamic suspicion timeouts and the buddy system; 50–100× fewer false positives in experiments.
4. Serf documentation: Gossip protocol internalsgithub.comHow Serf modifies SWIM: periodic TCP full-state sync, a separate faster gossip layer, keeping dead-node state, Lamport-clocked events.
5. hashicorp/memberlist: config.go (default LAN and WAN settings)github.comProbe, gossip, suspicion, retransmit and push/pull defaults and the formulas that scale them with cluster size.
6. Consul documentation: Gossipdeveloper.hashicorp.comLAN and WAN gossip pools and their ports, the gossip encryption key and its rotation, and Lifeguard.
7. Apache Cassandra documentation: Dynamo architecture (membership and failure detection)cassandra.apache.orgThe per-second gossip round, (generation, version) clocks, seed nodes, gossiped tokens and schema versions, and UP/DOWN as local decisions.
8. Apache Cassandra wiki: Architecture Gossipcwiki.apache.orgEndpoint state, heartbeat generation and version, and the SYN, ACK and ACK2 digest exchange, with a worked example.
9. Redis Cluster specificationredis.ioThe cluster bus, ping/pong gossip sections, the 100-node message arithmetic, PFAIL to FAIL by a majority of masters, and replica elections.
10. Dynamo: Amazon’s Highly Available Key-value Store (DeCandia et al., SOSP 2007)allthingsdistributed.comGossip-based membership every second, seeds against logical partitions, local failure detection and the cost of gossiping a full routing table.