A gossip protocol is a decentralized communication mechanism in which nodes in a distributed system periodically exchange information with a small, randomly selected subset of their peers. Over time, these repeated, pair-wise exchanges cause updates to spread through the network in an epidemic fashion, eventually reaching all nodes without requiring any central coordinator.
Key characteristics
Epidemic / probabilistic dissemination
Information does not follow a fixed route. Instead, each node “gossips” the update to a few peers, who gossip it to others, until the entire network converges.
Decentralized & fault-tolerant
No single node coordinates or controls propagation. Failure of individual nodes does not disrupt the protocol.
Eventually consistent
All nodes converge to the same state, but not necessarily at the same time.
Scalable
Because each node communicates with only a small number of peers at each round, gossip protocols scale to large networks with low overhead.
Redundant & robust
The random, redundant spreading ensures information reaches nodes even in the face of network partitions or failures.
Formal structure
A gossip protocol typically includes:
Push: a node sends its update to peers
Pull: a node requests updates from peers
Push-pull: a combination of both (fastest convergence)
And runs in discrete “rounds,” where each node:
Selects a random subset of peers
Exchanges state
Merges state
Repeats periodically