Commentary: gossip-protocol

"It reaches every node in O(log n) rounds" is true, which is exactly why it is not the result. Half the cluster costs 10.01 rounds; the last node costs 8.19 more, and 63.6% of every message ever sent goes to the final 5% of nodes. A study guide for gossip.py.

cd gossip-protocol
python3 demo.py         # the aha (§6) — about 25 seconds
python3 test_gossip.py  # pins every number this page claims — about 14 seconds

1. Orientation

This toy is an epidemic dissemination protocol — the mechanism under Cassandra's gossip, Consul and Serf's membership layer, Redis Cluster's heartbeat bus, and Amazon Dynamo's original failure detector. One node learns something; every node has to end up knowing it; there is no coordinator and no broadcast primitive. Each node, once per round, calls fanout uniformly random peers, and the news travels along that call.

Three directions the news can travel, all implemented here:

• push — the caller knows and tells the callee.
• pull — the caller doesn't know, asks, and learns if the callee does.
• push-pull — both, on the same call.

The three modes replay one identical contact schedule, so they disagree about the direction of travel and never about who talked to whom. The shortest version of the result:

from gossip import schedule, simulate

sched = schedule(1024, 1, 40, seed=0)          # one plan, replayed three ways
for mode in ("push", "pull", "pushpull"):
    left = [1024 - c for c in simulate(1024, sched, mode=mode)["curve"]]
    print(f"{mode:9s} rounds={len(left)-1:2d}  tail={left[-6:]}")
# push      rounds=20  tail=[5, 2, 1, 1, 1, 0]
# pull      rounds=13  tail=[681, 437, 165, 22, 1, 0]
# pushpull  rounds= 9  tail=[943, 809, 525, 165, 18, 0]

Read the push tail again. It sits at one ignorant node for three consecutive rounds while 1023 nodes gossip at full volume. Pull, on the same arrows, walks 681 → 437 → 165 → 22 → 1 → 0 and is finished.

By the end you should be able to:

• say why "O(log n) rounds" is true and useless, and what it costs to get the last 1% of a cluster instead of the first 99%;
• derive, without simulating, that a push epidemic with one node left clears it with probability 1 − 1/e per round, and pull with probability 1;
• state the one line of simulate that sets every constant on this page, and the three that look load-bearing and are measurably not;
• decide whether push, pull or push-pull is right for your SLO — and know that if your SLO is 90% coverage, the answer is "it barely matters";
• read GossipNodes and RetransmitMult in a memberlist config and know which number you are choosing.

2. The problem this mechanism exists to solve

A cluster has to agree on something small and constantly changing: who is alive, which node owns which shard, what the current config version is. The obvious designs both fail at scale. A coordinator that mails everybody is an O(n) bottleneck at one machine and a single point of failure. A reliable broadcast primitive over an unreliable network is expensive and, in practice, is what you were trying to avoid building.

Epidemic dissemination trades certainty for cheapness: every node tells a random peer, forever, and the news spreads like a disease. Demers et al. reached for it because the deterministic design had melted their network — "For a domain stored at 300 sites, 90,000 mail messages might be introduced each night. This was far beyond the capacity of the network, and resulted in breakdowns in all the network services."

The competing goals that make more than one design defensible:

• Time to full coverage. How many rounds until every node knows? This is the number people quote, and §6 argues it is the wrong one to design against.
• Total messages. Every node calling every round is n × fanout calls per round whether or not anyone learns anything. Message volume is what actually costs money, and it is dominated by the endgame.
• Robustness. Randomized contact means no node is critical, no link is critical, and a dropped message costs one round rather than correctness. This is what you are buying, and it is why "just use a spanning tree" is not the answer.
• Termination. Anti-entropy (a node that knows, gossips forever) always converges and never stops sending. Rumor-mongering (stop after k useless contacts) stops sending and does not always converge. §7 has the measured price.

3. Background you need

The three starred rows carry the result. Everything on this page follows from one asymmetry: under push, an ignorant node has to be found, and the probability of it being missed by all n−1 callers converges to 1/e. Under pull, the ignorant node does its own asking and cannot be overlooked.

4. The mental model

The whole page is that last picture. A push epidemic finishes when the last ignorant node is found by accident, and the cluster is paying full price for every round it spends looking.

5. Reading the source

The schedule comes first, because it is what makes the comparison honest:

def schedule(n, fanout, rounds, seed):
    """plan[r][i] = the `fanout` peers node i calls in round r.

    Peers are drawn with replacement from the other n-1 nodes: `j >= i` is
    bumped so a node never calls itself. Both of those are measured to be
    inert at n=1024 (see commentary section 5) — the schedule is generated
    up front purely so that push, pull and push-pull can replay it.
    """
    rng = random.Random(seed)
    plan = []
    for _ in range(rounds):
        row = []
        for i in range(n):
            peers = []
            for _ in range(fanout):
                j = rng.randrange(n - 1)
                if j >= i:
                    j += 1
                peers.append(j)
            row.append(tuple(peers))
        plan.append(tuple(row))
    return plan

Generating the contact plan up front rather than drawing peers inside the simulation loop is the single decision that makes this toy a comparison instead of three unrelated runs. Push, pull and push-pull consume the same plan, so "pull is 1.31× faster at full coverage" is measured against the identical set of arrows rather than against a different roll of the dice. Statisticians call this common random numbers; here it also means the seed-0 traces in §6.2 can be read side by side.

The two lines that look like judgement calls in this function — j >= i: j += 1 (never call yourself) and drawing with replacement so a fanout of 3 can draw the same peer twice — are both measured inert at n=1024, 200 seeds:

18.20 rounds against 17.89 if self-calls are allowed, and 8.19 against 8.19 for distinct vs. repeated peers. The docstring says so, because a reader is entitled to know which lines were tested and which were merely written.

The contract of simulate is where the toy's two accounting choices live:

def simulate(n, sched, mode="pushpull", max_rounds=None, start=0,
             lazy=False, live=False):
    """Run one epidemic over a fixed contact schedule.

    lazy   charge only the nodes with a reason to call. A push from a node
           with no news, or a pull by a node that already knows, cannot teach
           anyone anything, so this changes the bill and not the outcome.
    live   read the infection set live instead of from a start-of-round
           snapshot, letting a node infected earlier in this round spread
           within it. This is the load-bearing line; False is the honest
           model of a synchronous round.

    Returns a dict whose `curve[r]` is how many nodes know at the START of
    round r. A run that exhausts `max_rounds` comes back converged=False
    rather than looping until it finishes.
    """

max_rounds is not defensive programming. A gossip simulation that loops until convergence is a program that can hang, and the rumor-mongering variant in §7 genuinely never converges in 99% of runs — so "ran out of rounds" has to be a result the caller can read (converged=False), not a stall.

Now the loop itself, sixteen lines that contain the entire mechanism:

for r in range(cap):
    if known == n:
        break
    snap = inf if live else bytes(inf)   # <-- the load-bearing line
    calls += callers(mode, n, known, lazy) * fanout
    newly = set()
    for i, peers in enumerate(sched[r]):
        for j in peers:
            if mode != "pull" and snap[i] and not snap[j]:
                newly.add(j)
                inf[j] = 1
            if mode != "push" and snap[j] and not snap[i]:
                newly.add(i)
                inf[i] = 1
    known += len(newly)
    curve.append(known)

Three things are worth the space.

The two ifs are one mechanism read in two directions. mode != "pull" is the push arm: the caller has it, the callee doesn't, so the callee learns. mode != "push" is the pull arm, with i and j swapped. Push-pull is not a third algorithm — it is the same call with neither arm disabled, which is why it never loses to either.

snap = inf if live else bytes(inf) is the load-bearing line, and it is load-bearing in a specific, checkable way. Writes always go to inf; reads always go through snap. When snap is a copy, a node infected in round r cannot spread until round r+1 — a real synchronous round. When snap is inf, infection chains within a single round in node-index order. That one binding changes every constant on this page (200 seeds, checks/cf1_counterfactuals.py):

And here is why it is worth a paragraph rather than a caveat: the aha gets stronger under the variant. Push against push-pull goes from 1.98× to 2.28×. The line sets the constants; it does not manufacture the result. A counterfactual that flips the conclusion means the toy is about the line. One that moves the numbers and widens the gap means the toy is about the mechanism.

newly is a set, and known += len(newly) is why. Under push, two different callers can reach the same ignorant node in one round; the set de-duplicates them, so the coverage curve counts nodes and never double-counts an arrival.

The charging model is separated out on purpose, because it is the part of the measurement people argue about:

def callers(mode, n, known, lazy=False):
    """How many nodes actually place a call in a round that starts with
    `known` nodes informed.

    Naive accounting charges everybody every round. Lazy accounting is the
    steelman for push: a node with nothing to say stays silent, and under
    pull a node that already knows has nothing to ask for. Push-pull cannot
    be lazy — every node has one of the two reasons, always.
    """
    if not lazy or mode == "pushpull":
        return n
    return known if mode == "push" else n - known

Naive accounting ("everybody calls every round") makes push-pull look strictly dominant, and §6.6 shows that conclusion is false. A real push implementation does not wake up a node with no news to make an empty RPC, so charging it for one is not a model, it is a thumb on the scale. Note that lazy cannot change the coverage curve — a push from a node that knows nothing, and a pull by a node that already knows, are both no-ops in the loop above — which test_gossip.py::test_lazy_accounting_changes_the_bill_and_not_the_outcome asserts directly.

Finally, the accounting that turns a coverage curve into the aha:

def band_costs(curves, n, fanout, bands, mode="push", lazy=True):
    """Attribute every call placed to the coverage band its round STARTED in.

    A round that begins with c nodes informed places callers(...) * fanout
    calls and ends with curve[r+1] informed, so the spending and the nodes it
    bought are charged to the same band. That pairing is the entire cost
    argument: the bands cover equal fractions of the cluster at wildly
    unequal prices.
    """
    calls = {b: 0 for b in bands}
    gained = {b: 0 for b in bands}
    for curve in curves:
        for r in range(len(curve) - 1):
            frac = curve[r] / n
            for b in bands:
                if b[0] <= frac < b[1]:
                    calls[b] += callers(mode, n, curve[r], lazy) * fanout
                    gained[b] += curve[r + 1] - curve[r]
                    break
    return calls, gained

The break matters: bands are half-open and disjoint, so every round's spending lands in exactly one bucket and nothing is counted twice or dropped. test_gossip.py::test_band_costs_conserves_both_columns checks both columns against independent totals — sum(gained) == seeds × (n−1) and sum(calls) equal to the calls figure simulate returned — because a headline of "63.6% of messages" is worthless if the denominator quietly leaks rows.

6. The demo, and what it proves

python3 demo.py runs seven measurements at n=1024. Every table below is copied from its stdout. Seed counts are stated per section because they differ: 200 seeds for the main figures, 300 for the coverage-target sweep, 100 for the fanout sweep.

6.1 The claim everyone predicts correctly

200 seeds, push, fanout 1. r100/log2(n) sits between 1.820 and 1.859 across a 128× range of n. O(log n) is confirmed, and there is no toy in it, because that is what the reader already believed.

The last two columns are worth more than the confirmation. Demers gives the exact push constant: "For push, the exact formula is log₂(n) + ln(n) + O(1) for large n." That predicts 16.93 rounds at n=1024 and the toy measures 18.20, so this round model's O(1) is 1.26 — and it grows slowly with n (0.38, 0.83, 1.05, 1.28, 1.26) rather than being constant over this range. The asymptotic ratio is 1 + ln 2 = 1.693; the measured 1.82 is that plus O(1)/log₂ n. The column being flat is partly luck: the residue grows at almost exactly the rate that divides it out.

6.2 Where the time actually goes

Rounds to reach a given fraction of the cluster, 200 seeds:

Push reaches half of 1024 nodes in 10.01 rounds and needs 8.19 more for the last one. That is 8.19/18.20 = 45.0% of the wall clock spent after half the cluster already knows. Getting from 99% to 100% costs 3.05 rounds — more than getting from 0% to 25% costs (9.00 rounds gets you 256 nodes; 3.05 more rounds at the end gets you 10).

The seed-0 traces show it without any statistics. Same schedule, three directions, "nodes that still don't know":

Push spends rounds 17, 18 and 19 with exactly one ignorant node left, while 1023 nodes place 1023 calls per round. Pull's last three values are 22 → 1 → 0. Push-pull's are 165 → 18 → 0.

6.3 Where the messages actually go

Charging push only for calls a node had a reason to place (§5's lazy), and attributing each round's spending to the coverage band it started in — 200 seeds, per-seed averages:

Read the last column. The first quarter of the cluster costs 1.2 calls per node informed. The last 1% costs 492.2 — a factor of 396. Rounds that began at ≥90% coverage burn 63.6% of the entire message budget to inform 53.4 of 1023 nodes, or 5.2% of the cluster.

The arithmetic is not subtle once you see the shape. A round starting with c nodes informed costs c calls under lazy push and gains c'−c nodes, so the unit price is c/(c'−c). Early on, c' ≈ 2c, so the price is about 1 call per node. At the end, c = 1023 and c'−c is at most 1, so the price is at least 1023 calls per node — and averaged over the runs that spend more than one round there, 492.2 for the last band as a whole. The cluster does not slow down at the end. It keeps working at exactly the same rate and stops buying anything.

6.4 Why: two decay laws, one of them quadratic

Take the residual s — nodes that still don't know — and ask what one round does to it. Start with the extreme case, one node left:

That is the whole asymmetry in four lines. Under push, 1023 nodes fire 1023 calls at 1023 possible targets and the one that matters is missed by all of them with probability 0.3677 — which is 1/e to three decimals, and is 1/e for the usual reason, (1 − 1/m)^m → e⁻¹. So the epidemic sits at residual 1 for 1/(1−0.3677) = 1.582 rounds in expectation. Under pull, the last ignorant node places its own call, and every peer it could possibly reach already knows: probability 1023/1023 = 1.000, one round, always. The measurement is exact — no pull run in 200 spends more than a single round at residual 1, and at 1000 seeds it is still 204/204 runs at exactly 1.000 while push's mean converges toward the predicted 1.582:

Generalize from residual 1 to every residual, by pooling every s → s' transition across 200 seeds and bucketing by s:

Push divides the residual by a constant. Pull squares it. push s'/s sits at 0.365–0.408 for every small bucket, against 1/e = 0.368. The pull s' column tracks the predicted s²/n — 2.15 against 2.13, 8.26 against 8.12, 37.93 against 35.79 — at every bucket where there is data.

Dividing by a constant costs ln(n) rounds to clear. Squaring costs log log n. That is the entire push/pull story, and it is not this toy's discovery — it is Demers' 1987 recurrence, measured. The paper derives pi+1 = (pi)² for pull and pi+1 = pi(1 − 1/n)n(1−pi) for push, "which also converges to 0, but much less rapidly, since for very small p_i (and large n) it is approximately pi+1 = pie⁻¹". Karp et al. put the same thing in mean-field form: u ≈ exp(−t/n) for push against u ≈ exp(−2t) for pull — an exponential against a double exponential.

6.5 The first boundary: your SLO decides whether any of this matters

Push/pull ratio by coverage target, 300 seeds per size:

At 50% coverage push is faster than pull at every size (0.852–0.977). At 75% they are within 2.2% either way (0.991–1.021), and which side of 1.0 the crossing lands on flips with n — 1.014 and 1.021 at n=32 and 1024, but 0.994 and 0.991 at n=8 and 128. Do not read that column as monotone; it isn't. At 90% pull is ahead by 6–19%. Only at 100% does pull win clearly (1.19–1.31).

So: if your SLO is "90% of nodes have the new config within X", the direction of the arrow is worth a few percent and you should spend your attention elsewhere. Pull's entire advantage lives in the last 10% of nodes, and if you never wait for the last node, you never collect it. This is where the effect vanishes — and it vanishes at a coverage target most systems actually care about.

6.6 The second boundary: fanout, and a claim that did not survive

Under naive accounting push-pull looks strictly dominant, and the tempting sentence is "push-pull is free." Steelman push instead — a node with nothing to say places no call — and run the fanout sweep, 100 seeds:

Lazy push at fanout 3 beats push-pull at fanout 1 on both axes: 8.21 rounds against 9.18, and 9,285 calls against 9,400. "Push-pull is free" is false, and it is the sentence this page would have shipped without the run.

What replaces it is better. Fanout is nearly free. Going from fanout 1 to fanout 5 makes push 3.0× faster (18.20 → 6.07 rounds) for 21.6% more messages (8,302 → 10,100). That looks impossible until you remember §6.3: almost the whole message budget is spent in the endgame, so shortening the endgame pays for the extra calls in the rounds that remain. Fanout buys time at nearly no cost, and switching arrow direction buys a little time at a structural cost — which is the practical ranking most production systems have independently arrived at.

7. Design decisions and roads not taken

One schedule, three modes. The alternative — draw peers inside the simulation — would make each mode's run an independent sample, and a 1.31× difference measured that way is a claim about two random variables rather than about the mechanism. Sharing the schedule is what lets §6.2's three traces sit under each other and be the same experiment.

The snapshot, not live state. Reading inf live is not "wrong" — it is a different model, closer to a system where a node forwards on receipt within the same tick. The toy takes the snapshot because a synchronous round with simultaneous exchange is the model the analysis in every paper cited here assumes, and because a live read makes the outcome depend on node index order, which is an artifact of the loop rather than of the protocol. The counterfactual is in §5 and it makes the aha stronger, not weaker.

Lazy accounting ships, and is the default in band_costs. It is the honest bill and it kills a wrong claim (§6.6). It also makes the concentration worse, not better: under naive charging the ≥90% bands hold 28.8% of the budget and the last-1%-vs-first-25% ratio is 20×, against 63.6% and 396× under lazy (checks/cf4_selfcheck.py). Charging idle nodes for silence hides the skew by inflating the cheap rounds.

Rumor-mongering is not in the toy. Demers' fix for the expensive endgame is to have a node stop spreading after k contacts that taught nobody anything, converting an "infective" node to "removed". It is the natural next question after §6.3, and it is a second mental model — the toy would grow a third state, a staleness counter, and an entirely different failure mode. It is measured, though, in checks/cf2_mongering.py (n=256, push, fanout 1, 200 seeds, hard cap 60 rounds):

k=3 saves 38% of the messages (1061 against 1707) and 99.0% of runs never converge at all, stranding a mean of 4.1 nodes permanently — the epidemic dies while nodes are still ignorant, and no amount of waiting fixes it, because nobody is still spreading. You buy message savings with correctness, continuously, and there is no k that is free. Push-pull is far more robust to the same cutoff: at k=3 it converges in 200/200 runs where push needs k=12, because an ignorant node initiates its own pull and cannot be overlooked.

One rumor bit, not a database. Real anti-entropy reconciles whole key-value states, which is why Demers spends pages on checksums, recent-update lists and "peel back". A single bit keeps the toy about dissemination dynamics; adding reconciliation would double the code and teach a different mechanism (that one is merkle-tree).

A hard max_rounds, and non-convergence as a return value. Every sweep in demo.py caps rounds and asserts convergence, so a pathological seed is a loud assertion rather than a hang. The mongering script above is the reason this is not optional.

Deliberately absent: node failures and partitions, join/leave churn, message loss, asynchronous per-node timers, network delay, topology (Demers' "spatial distributions" that favor nearby peers). Each is a real production concern and each would be a second mechanism in one file.

8. What's simplified vs. the real thing

• A round is not a second, and real gossip is not synchronous. Cassandra's gossiper runs a task "every second" in which each node "picks a random other node in the cluster to exchange gossip endpoint state with" — independently, with no global round boundary. The synchronous round is a modelling convenience that makes the residual recurrence exact; the real thing has drift, and nodes that gossip twice while a neighbour gossips once.
• Real systems piggyback rather than gossip a lone rumor. SWIM — the protocol under Serf, Consul and memberlist — makes exactly this trade: "Information about membership changes, such as process joins, drop-outs and failures, is propagated via piggybacking on ping messages and acknowledgments." The failure detector's traffic is already flowing, so dissemination is nearly free; this toy's message counts assume a call carrying nothing else.
• Fanout is a config knob with a documented cost. memberlist's GossipNodes is literally this toy's fanout — "the number of random nodes to send gossip messages to per GossipInterval. Increasing this number causes the gossip messages to propagate across the cluster more quickly at the expense of increased bandwidth." §6.6 is what that sentence costs numerically.
• Rumor-mongering ships in production, scaled by cluster size. memberlist's RetransmitMult sets retransmissions as RetransmitMult * log(N+1) — the k of §7, deliberately grown with n so that the stranding rate stays low as the cluster grows. The toy's fixed k is what makes its failure so stark.
• Real clusters bound message volume differently. Redis Cluster does not gossip a rumor at all in this sense — "a node will ping a few random nodes every second so that the total number of ping packets sent (and pong packets received) by each node is a constant amount regardless of the number of nodes in the cluster," with a NODE_TIMEOUT-driven guarantee layered on top. That is a per-node-bandwidth design, where this toy is a per-round design.
• No failures, no loss, no partitions. Message loss under push costs a round; under a partition, an epidemic simply does not cross it, and the membership layer is what notices. Every real gossip implementation spends most of its code there, not here — see failure-detector.
• n is known and fixed. Real nodes gossip about membership, so the peer list is itself the thing being disseminated, and a node that joins mid-epidemic is both a target and a carrier.
• One process, one thread, no network. No serialization, no concurrency, no partial delivery. simulate is a bytearray and two ifs.

9. Check yourself

10. Further reading

Every link below was fetched and confirmed live when this was written.

• Demers et al.: Epidemic Algorithms for Replicated Database Maintenance (Xerox PARC CSL-89-1, the tech-report version of the PODC '87 paper) — the source of everything on this page. Page 6 has both recurrences this toy measures: pi+1 = (pi)² for pull, and for push pi+1 = pi(1 − 1/n)n(1−pi) which "converges to 0, but much less rapidly, since for very small p_i (and large n) it is approximately pi+1 = pie⁻¹". It also states the exact push constant log₂(n) + ln(n) + O(1) that §6.1 checks, and — page 7 — the conclusion this toy spends §6.6 disputing at fanout > 1: "either pull or push-pull is greatly preferable to push, which behaves poorly in the expected case." Read §1.4 for rumor-mongering and §2 for why deletions need death certificates.
• Karp, Schindelhauer, Shenker, Vöcking: Randomized Rumor Spreading (FOCS 2000) — the theory that turns §6.4's two columns into bounds. "In other words, a push algorithm needs Θ(n ln n) transmissions for sending a rumor to all players"; push's mean-field decay is u ≈ exp(−t/n) against pull's u ≈ exp(−2t), and "this double exponential behavior implies that only Θ(n ln ln n) transmissions are needed if the distribution of the rumor can be stopped at the right time." The paper then does the thing this toy can't: an algorithm "using only O(n ln ln n) transmissions and O(ln n) rounds", plus a matching lower bound for address-oblivious algorithms.
• Das, Gupta, Motivala: SWIM — Scalable Weakly-consistent Infection-style Process Group Membership Protocol (DSN 2002) — what the industry actually deploys. The key design move is in the abstract: membership updates are "propagated via piggybacking on ping messages and acknowledgments", so dissemination rides the failure detector and costs nothing extra. Read it for the separation of detection from dissemination, which this toy collapses.
• HashiCorp memberlist — Config reference — this toy's parameters as production config. GossipNodes is fanout ("the number of random nodes to send gossip messages to per GossipInterval"); RetransmitMult is rumor-mongering's k, with the retransmit count computed as RetransmitMult * log(N+1) so it "scale[s] properly with cluster size". §7's stranding table is why that log is there.
• Consul: Gossip Protocol — the operator-facing view of the same thing, including Lifeguard (the extension that stops a slow node from being declared dead) and the LAN/WAN pool split, which is Demers' spatial distribution idea in production form.
• Apache Cassandra: Dynamo — Gossip — "Every second, every node in the cluster" runs the gossip task and "picks a random other node in the cluster to exchange gossip endpoint state with", with state versioned by (generation, version) tuples. Fanout 1, once per second, at every node: the exact configuration §6 measures.
• Redis Cluster specification — heartbeat and gossip messages — the counter-design: "a node will ping a few random nodes every second so that the total number of ping packets sent … by each node is a constant amount regardless of the number of nodes in the cluster", with a NODE_TIMEOUT/2 sweep on top. Worth reading beside §6.3 as a system that bounds per-node bandwidth and accepts the coverage consequences.
• Wikipedia: Gossip protocol — the folk statement in its own words: "within logarithmic time in the size of the network … any new search string will have reached all agents." True, and §6.1 is what it leaves out.

Elsewhere in this repo, failure-detector is the other half of a real membership layer — this toy assumes every node is alive and reachable — and consistent-hashing is the other page where a true average ("about 1/N of the keys move") hides everything that matters about the distribution.