Gossip protocol
On the roadmap:Advanced · step 4: Distributed systems
Nodes spread an update by repeatedly exchanging state with a few random peers; the whole cluster converges in about log N rounds.
In plain words
Servers spread news the way rumours spread: each one regularly tells a few random neighbours what it knows, and soon everyone does.
Why it matters
No central coordinator is needed, and it keeps working when machines fail. The cluster agrees quickly, and the message cost per machine stays small even for large clusters.
Where you meet it
- Cassandra and Consul for cluster membership
- Redis Cluster for sharing node state
- Systems that detect which nodes are alive
You will be able to
- Explain why news reaches every node in roughly log N rounds
- Merge two copies by keeping the higher version
- Compare gossip with broadcasting to everyone
In interviews
Used for 'how do nodes learn who is alive?' in distributed databases and service discovery.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- Nodes that hold versioned key-value records
- A round: each node picks a few random peers
- Push-pull merge: both sides keep the higher version
- A seeded random generator, so the run is repeatable
export type Rec = { value: string; version: number };
/** Small seeded random generator (mulberry32), so simulations repeat exactly. */
export function rng(seed: number) {
return () => {
seed = (seed + 0x6d2b79f5) | 0;
let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
};
}
export class Cluster {
nodes: Map<string, Rec>[];
private rand: () => number;
constructor(size: number, private fanout = 2, seed = 1) {
this.nodes = Array.from({ length: size }, () => new Map());
this.rand = rng(seed);
}
/** A write lands on one node only. */
put(node: number, key: string, value: string): void {
const cur = this.nodes[node].get(key);
this.nodes[node].set(key, { value, version: (cur?.version ?? 0) + 1 });
}
private merge(a: Map<string, Rec>, b: Map<string, Rec>): void {
for (const [k, r] of b) if (!a.has(k) || a.get(k)!.version < r.version) a.set(k, r);
}
/** One synchronous gossip round: every exchange reads the state from the start of the round. Returns the number of exchanges. */
round(): number {
const before = this.nodes.map((n) => new Map(n));
let msgs = 0;
for (let i = 0; i < this.nodes.length; i++) {
for (let f = 0; f < this.fanout; f++) {
let j = Math.floor(this.rand() * this.nodes.length);
if (j === i) j = (j + 1) % this.nodes.length;
this.merge(this.nodes[i], before[j]); // pull from the peer
this.merge(this.nodes[j], before[i]); // push to the peer
msgs++;
}
}
return msgs;
}
converged(key: string, value: string): boolean {
return this.nodes.every((n) => n.get(key)?.value === value);
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints gossip-protocol ok when everything passes. You need Node.js installed.
mkdir gossip-protocol && cd gossip-protocol
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Production gossip, such as the SWIM-style protocols in Consul and Serf, is mostly about spotting failures: nodes also ping each other and share suspicions about who is down.
- Cassandra uses an accrual failure detector, which gives a suspicion level that rises with silence instead of a hard alive-or-dead answer.
- Messages are kept small by sending digests and only the differences, and cluster membership changes are versioned.
Ways to spread information in a cluster
| How news spreads | Failure behaviour | Cost | Pick it when | |
|---|---|---|---|---|
| Gossip | Random peers swap news each round; everyone knows in about log N rounds | No single point of failure | Small, steady load per node | The cluster is large or changes often |
| Central coordinator | One service holds the truth and others ask it | If it fails, everyone is stuck | The coordinator gets all the traffic | The cluster is small |
| Broadcast to everyone | The sender tells every node directly | The sender is a bottleneck | N messages from one node | Tiny clusters |
| Consensus (Raft, Paxos) | Nodes agree on one value and one order | Survives a minority failing | More messages and a majority is needed | You need one agreed answer |
What it cannot do
Only eventually consistent
For a while some nodes know and some do not. It never says 'everyone knows now'.
The timing is random
Spreading takes a few rounds on average, not a guaranteed number.
It needs versions
Without a version or timestamp, nodes cannot tell which of two values is newer.
It cannot choose a leader
Agreeing on one value needs consensus, not rumours.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Add node failures and see convergence slow down
- Add a heartbeat counter and detect dead nodes
- Count messages per round and compare with broadcast