The Rumor Needs a Fanout
A broadcast tree has a foreman. A rumor has witnesses.
That is the practical difference between a centralized dissemination path and a gossip protocol. The central path tries to name who forwards to whom. Gossip lets each participant sample a few peers, repeatedly, and trusts probability to fill in the missing edges.
The shape is old. Demers, Greene, Hauser, Irish, Larson, Shenker, Sturgis, Swinehart, and Terry used epidemic algorithms for replicated database maintenance at Xerox PARC: anti-entropy reconciled replicas by pairwise exchange, while rumor mongering tried to spread recent updates cheaply before a slower repair mechanism cleaned up the residue.1 The idea survived because it has the rare engineering smell of being both crude and useful.
The price is that “fanout 1” is not the same promise as “everyone hears it.” It is a stochastic contact budget.
The Random Phone Call Model
The clean model is almost suspiciously small:
there are n nodes
one node starts informed
time moves in rounds
each active node calls a few random peers per round
successful contacts transfer the rumor
This model deliberately ignores membership churn, topology, congestion, message size, authentication, retries, backpressure, and whether the rumor is an update, a membership change, or a cache invalidation. That is not because those details are unimportant. It is because the core tradeoff appears before they enter.
Push is good when the rumor is rare. One informed node calls one peer; then two informed nodes call; then four. Early growth looks like a branching process.
Push is bad when the rumor is common. Once almost everyone has heard it, most push contacts land on nodes that already know. The last few uninformed nodes are hard to hit by accident.
Pull is the mirror image. It is weak at the beginning because uninformed nodes are mostly calling other uninformed nodes. It becomes excellent near the end because the few remaining uninformed nodes are surrounded by informed peers.
Push-pull combines the two. Karp, Schindelhauer, Shenker, and Voecking studied this random phone-call setting and made the time/work tradeoff explicit: random contacts can be fast, but they cannot be both perfectly time-optimal and communication-optimal for free.2
The curve has three regions:
startup: one rumor carrier has to create a second carrier
growth: informed nodes multiply quickly
cleanup: the last uninformed nodes dominate the schedule
Most production pain lives in the cleanup region.
Lab: Spend The Contacts
The lab below runs deterministic Monte Carlo trials for three policies on a complete random-peer model:
push: informed nodes call random peers
pull: uninformed nodes call random peers
push-pull: every node calls random peers; either side can teach the other
The plotted curves are averages across trials. A contact is counted whether or not it carried new information; dropped contacts are counted as work too. The model is intentionally simple enough to audit.
Deterministic simulation. The audit checks monotone coverage, population bounds, and broad push-pull coverage across the configured trials.
At the default setting, there are 512 nodes, one initial holder, fanout 1,
and a 4% independent contact drop rate. The exact numbers move with the seed,
but the shape is stable: push-pull usually reaches 99% coverage in far fewer
rounds than pure push or pure pull, and the late-stage redundancy is visible.
Raise Drop rate. Coverage remains graceful for a while because the protocol keeps taking new random shots. Raise Fanout. Time drops, but contacts per node rise. The knob is not “reliability”; it is how much random work you are willing to buy per round.
You can reproduce the audit from Node:
const lab = require("./assets/js/gossip-fanout-lab.js");
const audit = lab.auditGossipFanoutLab();
const failed = audit.cases.filter((row) => !row.passed);
if (failed.length || audit.passed !== audit.total) {
throw new Error(JSON.stringify({
failed,
passed: audit.passed,
total: audit.total
}, null, 2));
}
console.table(audit.cases.map((row) => ({
scenario: row.label,
nodes: row.nodes,
fanout: row.fanout,
lossPct: row.loss,
trials: row.trials,
push99: row.pushT99.toFixed(1),
pull99: row.pullT99.toFixed(1),
pushPull99: row.pushPullT99.toFixed(1),
pushPullP90: row.pushPullP90Round99,
pushPullReached: String(row.pushPullReached99) + "/" + row.trials,
contactsPerNode99: row.pushPullContactsPerNode99.toFixed(2),
redundantShare99: row.pushPullRedundantShare99.toFixed(2)
})));
The grid checks lossless, moderate-loss, larger-population, and high-loss cases. It asserts monotone coverage, population bounds, a single initial holder, and enough push-pull 99% coverage when the configured loss rate is not intentionally extreme.
The source is intentionally small:
assets/js/gossip-fanout-lab.js.
Why Push And Pull Trade Places
Let (i_t) be the informed fraction at the start of a round.
In a pure push model with fanout one and no loss, each informed node chooses a random peer. A particular uninformed node is missed by all informed callers with probability roughly:
\[\left(1 - {1 \over n}\right)^{n i_t} \approx e^{-i_t}.\]So the chance it becomes informed is about (1-e^{-i_t}). When (i_t) is small, this is close to (i_t), which gives exponential-looking growth. When (i_t) is near one, the remaining uninformed fraction shrinks by a constant factor per round. That is progress, but it is tail progress.
In pure pull, each uninformed node asks one random peer. It becomes informed with probability (i_t). Early on, (i_t) is tiny, so pull waits. Near the end, (i_t) is large, so almost every uninformed node that asks gets the rumor.
Push-pull uses both facts. It pushes the seed through the branching phase and pulls the tail closed.
This is also why the word “eventual” can hide two different meanings:
eventual with repair: anti-entropy keeps reconciling until residue is gone
eventual with rumor: likely fast, but some residue may need a backup
Demers et al. made that distinction explicitly: rumor mongering can be an efficient first wave, but anti-entropy is the mechanism that guarantees complete coverage of the missed residue.1
The Tail Is Not A Bug
If a cluster has 10,000 nodes and 9,990 already know an update, the update is not “basically done” from the perspective of the ten remaining nodes. Those ten nodes may be exactly the replicas, caches, or membership observers that make a future incident confusing.
The tail is where redundancy becomes visible. Most random contacts no longer teach anyone anything. That does not mean they were mistakes. They are the price of not maintaining a precise broadcast tree and not requiring global coordination.
There are several ways to spend less:
stop early and rely on anti-entropy later
increase fanout for fewer rounds
track acknowledgments or rumor age
prefer topologically nearby peers
maintain partial views instead of sampling the whole population
Each choice changes the contract. A peer selection distribution that favors nearby nodes can reduce expensive links, but it can also make the last distant node harder to reach. The PARC paper is unusually grounded here: it studies nonuniform spatial distributions because real networks have costly links, not because uniform random choice is aesthetically wrong.1
Membership Is A Different Rumor
SWIM is a good example of the pattern in a different coat. It separates failure detection from membership update dissemination. Nodes periodically probe random peers, while membership changes are spread infection-style by piggybacking on protocol messages.3 That separation matters. Detecting a failed process and disseminating the fact of that detection are different jobs.
The lab is not a SWIM simulator. It has no suspicion state, no incarnation numbers, no indirect pings, and no false-positive model. It only shows the dissemination substrate: repeated random contact makes local knowledge become common-enough knowledge without a central sender.
That “enough” deserves respect. Gossip is often the right background fabric for membership, cache invalidation, metric sketches, and eventually consistent replication. It is not a magic replacement for consensus, durable logs, or linearizable reads.
The Operational Question
When I see a gossip knob, I want to know what it buys:
fanout: contacts per round per active node
period: wall-clock spacing between rounds
loss model: what counts as a failed contact
stop rule: when an informed node goes quiet
repair path: what fixes the residue
peer sampling: uniform, topology-aware, or partial view
payload: full state, digest, delta, or pointer
The implementation may be only a few lines of random peer selection. The contract is not. Every one of those choices moves load, convergence time, and tail probability.
That is the honest lesson of epidemic dissemination. The rumor does not need a foreman. It does need a fanout, a repair story, and a clear account of what “everyone heard” is allowed to mean.
-
Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry, “Epidemic Algorithms for Replicated Database Maintenance”, Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, 1987. ↩ ↩2 ↩3
-
Richard Karp, Christian Schindelhauer, Scott Shenker, and Berthold Voecking, “Randomized Rumor Spreading”, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000. ↩
-
Abhinandan Das, Indranil Gupta, and Ashish Motivala, “SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol”, DSN, 2002. ↩