Two random peers swap, and the newer copy wins
No leader, no schedule. Every interval, each node does this with k random peers, the fanout: k messages, at 50 nodes or 5,000.
≈ 9 s
for one update to reach 1,000 nodes
Fanout 3, a round a second. The count grows up to 4× a round, then mops up stragglers. 10× the nodes adds about two rounds.
What do you gossip for a count?
Bad: The operation: orders +1
Resends and duplicates each add another order.
Good: Each node’s own total
A: 41, B: 17. Keep the newest version per entry; duplicates change nothing.
Rumours are cheap because they die: each node stops after 3 calls to people who already knew.
The catch
Some never hear: 1.1% of 1,000 sites. Rare anti-entropy, a full-state sync, catches the rest.
SWIM: suspect before you declare dead
- Ping one random peer
- No ack? Ask three others to ping it
- Still silent? Mark it suspect, and gossip that
- It refutes with a higher incarnation, or it’s confirmed dead
Each node sends 3 messages a round, at 1,000 nodes or 10,000. Flat load forever?
The limit
Only if messages stay small. A full digest grows with N: 10× the nodes, 100× the traffic. Gossip deltas.
Gossip spreads opinions. It never decides.
A split cuts 10 nodes into 6 and 4; each side declares the other dead. Fine for routing reads. For a leader, gossip has no quorum: both sides act.
The line to say
Gossip reaches every node in O(log N) rounds at flat per-node cost. It spreads opinions; leaders and locks need consensus.