Gossip dissemination

One machine tells a few, they each tell a few, and the whole fleet knows in a handful of rounds.

The idea

A release tool has a build on one machine and five thousand machines that need it. If that one machine copies to each of them in turn, it makes five thousand transfers back to back and the last machine waits for all of them.

Gossip flips the work around. Every machine that already has the build is a sender. In each round, each of them pushes to a few machines that do not have it yet. So the number of machines holding the build multiplies every round instead of growing by one.

Multiplying reaches the whole fleet in a number of rounds that grows like a logarithm. Ten times the machines costs one or two more rounds, not ten times the wait.

Machines 32 Fanout 2

How it works

Each round multiplies the informed set by one plus the fanout: every machine that has the build keeps it and adds up to fanout more. Counting rounds is then a matter of asking how many times you can multiply before you cover the fleet.

def rounds_to_cover(n, fanout):
    """Rounds for one seed to reach every machine, pushing to `fanout` each round."""
    informed, rounds = 1, 0
    while informed < n:
        # every informed machine pushes to fanout machines that lack the build,
        # so the informed set multiplies rather than grows by one
        informed = min(n, informed * (1 + fanout))
        rounds += 1
    return rounds

rounds_to_cover(5000, 3)   # 7
rounds_to_cover(5000, 1)   # 13

That is the ideal push: nobody wastes a send on a machine that already has the build. Real gossip picks peers at random and does waste some, which changes the message count but not the shape of the round count.

Cost

What	Gossip, fanout f	One sender
Rounds to cover n	log(n) / log(1+f)	n - 1
Transfers, ideal	n - 1	n - 1
Transfers, random peers	O(n log n)	n - 1
Load on the seed	f	n - 1

The trade is duplicate work for time. Gossip may send a machine something it already has, and in exchange no single machine is a bottleneck and the wait grows like a logarithm.

Watch out for

Random peers duplicate, and the tail is where it hurts. Real nodes do not coordinate who they push to. Early rounds almost always find someone new; late rounds mostly hit machines that already have the build, which is why the last few percent of a fleet costs a disproportionate share of the messages.
Fanout 1 still works, and it is fragile. Doubling is logarithmic, so one is enough on paper. But one dead peer removes an entire branch of the wave for that round. Two or three is the usual floor for that reason, not for speed.
A partition converges twice. Each side of a network split gossips happily to itself and reports healthy round counts. Nothing in the protocol notices that half the fleet is missing, so coverage has to be measured against the expected machine count, not against the machines you can reach.
A round is as slow as its slowest transfer. The round count is the theory; the wall clock is rounds multiplied by the slowest link in each one. One saturated machine stretches every round it takes part in.
Counting the seed. The fleet starts with one machine already holding the build, so the loop condition is informed < n starting from 1, not from 0. Starting the count at zero adds a phantom round.

Worked example

Five thousand machines, fanout three. After round one, four machines have the build. After round two, sixteen. The informed count is 4^r, and 4^6 is 4,096 while 4^7 is 16,384, so the fleet is covered in seven rounds.

Now double the fleet to ten thousand. 4^7 is still 16,384, so it is still seven rounds. The single sender, meanwhile, went from 4,999 transfers in sequence to 9,999. That is the whole argument for gossip in one comparison.

Check yourself

A rollout by gossip with fanout 3 covers a 1,000 machine cluster. The company grows and the cluster doubles to 2,000. How many more rounds does the rollout need?