How Fast Does Information Spread?
You might assume that random, uncoordinated sharing is slow. It is actually remarkably fast. The time it takes for a piece of information to reach all $N$ nodes in a cluster grows as $O(\log N)$ — logarithmic in the cluster size.
To make this concrete:
- 1,000 nodes → ~10 gossip rounds to reach full propagation
- 1,000,000 nodes → ~20 gossip rounds
If each round takes one second, a cluster one thousand times larger takes only twice as long to fully inform. This is the same reason doubling the world's population would only add one more "degree of separation" in the six-degrees-of-separation model.
The Fan-Out Parameter
Each node gossips to a fixed number of peers per round, called the fan-out (commonly denoted $k$, typically 3). Increasing $k$ speeds up propagation but increases bandwidth. The $O(\log N)$ bound holds for any constant $k \geq 2$. In practice, $k = 3$ is the sweet spot used by systems like Cassandra and Consul — it provides fast convergence with minimal overhead.
Consistency Guarantee
Gossip provides Eventual Consistency. It does not guarantee that every node learns about a failure or state change at the same instant. It guarantees that every node will learn about it — typically within a few seconds. This is an explicit trade-off: you sacrifice the coordination overhead of strong consistency (which requires synchronous acknowledgment from all nodes) in exchange for linear scalability and fault tolerance. Systems that use gossip for membership — Cassandra, Riak, Consul, etcd's peer discovery — all accept this trade-off because the alternative (a central coordinator) is a single point of failure.
Key Point: The $O(\log N)$ convergence bound assumes nodes gossip independently and randomly. If nodes gossip in correlated patterns (e.g., always preferring nearby nodes), convergence degrades. Production implementations deliberately randomize peer selection to maintain the mathematical guarantee.