Gossip Protocols

1000 nodes in a Cassandra cluster. Each needs to know about the others — who's alive, what ranges they own, their load. Centralized approach (one server polls all 1000) creates a SPOF and a bottleneck. Broadcasting (each node tells all 999 others) creates N² messages — 1M pings per cycle. Neither scales.

Gossip protocols (based on epidemic spreading) are the middle way: each node randomly picks a few peers each second, exchanges state, and in logarithmic time the whole cluster learns everything. It's what Cassandra, DynamoDB internal, Consul, Redis Cluster, and Hashicorp Serf all use for membership and failure detection.

Every second, each node picks K random peers (typically K=1–3) and exchanges its full view of the cluster. If node A knows "B is down," and A tells C, then C tells D next tick, by tick 3 everyone knows in a 1000-node cluster.

The math: with K=1, rumor propagation time is O(log N). 1000 nodes → 10 ticks → ~10 seconds. Small K, cluster-wide consistency in seconds, without any central coordinator.

Each node maintains a membership list: every node's ID, status (alive / suspect / dead), heartbeat timestamp, and metadata (token range, load, version). Gossip exchanges swap these lists — whoever has the fresher entry (higher heartbeat or newer version) wins.

Three typical payload types:

• Membership — who's in the cluster. Nodes join by gossiping their existence; peers propagate.
• Failure detection — heartbeats. Each node bumps its own heartbeat counter; peers gossip the latest heartbeat they've seen. Old heartbeat → suspect → dead.
• State — application-level data (token ranges, schema version, load averages).

Most production gossip protocols (Serf, Cassandra, Consul) use push-pull. It halves the convergence time compared to push-only.

SWIM (Scalable Weakly-consistent Infection-style Membership, Das et al., 2002) is the most common failure-detection gossip variant. Used in Serf, Memberlist (Consul, Nomad), and many others.

Each tick, every node picks one random peer and sends a ping. If no response within timeout, node sends indirect pings through K random other peers ("hey, can you ping this guy for me?"). If indirect pings also fail, mark suspect. After more ticks without hearing from it, mark dead.

The indirect-ping trick is the key insight: a direct ping might fail because of network flap between me and target. But if three other random nodes also can't reach it, it's probably actually dead. This gives much lower false-positive rates than "one missed ping = dead."

Propagation. Membership changes (joined, suspect, dead) ride as piggyback payload on regular ping-ack exchanges. No separate broadcast. Epidemic-style spread means all nodes learn in O(log N) ticks.

• Strong consistency. Gossip is eventually consistent — use Raft/Paxos when you need "exactly one leader" or "majority-agreed value."
• Low-latency writes. New info spreads in seconds, not microseconds. Don't gossip per-request data.
• Bandwidth-sensitive. Each tick exchanges full membership state. At 10k nodes the membership list itself is MBs. Hybrid designs (SWIM + delta-only gossip) manage this.

Count active users uses gossip-like approximation algorithms (HyperLogLog unions). Distributed logging uses gossip for log-ingest membership.