Gossip protocols & epidemic dissemination

Click "gossip one round" a few times. Node 0 tells a couple of neighbors, then those nodes each tell a couple more — the highlighted ring shows exactly who just heard the news this round. Nobody ever had to contact all 8 nodes directly; the rumor spreads through the network itself.

In an anti-entropy / push gossip protocol, every node that knows a piece of information (is "infected") contacts a small, bounded number of peers — its fanout — each round. Any peer it contacts becomes infected too, and joins in spreading next round:

• $I_t$ — the set of nodes that have heard the rumor after round $t$ (round 0 is just the one starting node).
• $\text{gossip}(v, t, k)$ — the up-to-$k$ peers node $v$ contacts during round $t$, drawn from its fixed neighbor list.
• $k$ — the fanout: how many peers each infected node contacts per round.

1. Growth compounds, it doesn't add

   Because every currently-infected node gossips simultaneously each round — not just the original source — the infected set can multiply round over round instead of only growing by a fixed amount, the way epidemics spread through a population.

2. Fanout trades speed for chatter

   A larger fanout reaches full coverage faster, at the cost of more messages sent per round. A fanout of 1 is the cheapest per round but the slowest to converge; a fanout equal to a node's full degree (flooding) is fastest but sends the most messages.

Drag the fanout slider down to 1, gossip forward, and watch how much longer it takes to reach every node — and how it can even stall for a round with nothing new happening, simply because this round's rotation of peers hasn't reached the last holdout yet. Push fanout up to 3 and the same 8-node network gets fully infected in half the rounds.

Same fixed 8-node network (each node has exactly 3 neighbors — a ring plus one long "shortcut" to the node directly opposite it), starting from node 0:

1. Fanout 2, round by round

   Peer selection rotates through each node's neighbor list by offset = round mod 3, contacting the next 2 neighbors from there:

   1. Round 1 (offset 0): node 0's neighbors are $[1,4,7]$, so it contacts the first two, $1$ and $4$ → infected $=\{0,1,4\}$
   2. Round 2 (offset 1): node 0 contacts $[4,7]$ (its neighbors shifted by 1), node 1 contacts $[2,5]$, node 4 contacts $[3,5]$ → infected grows to $\{0,1,2,3,4,5,7\}$ — seven of eight
   3. Round 3 (offset 2): nodes 2, 5, and 7 each shift to contacting $6$ as one of their two targets — the last holdout finally gets reached → all 8 nodes infected
2. Fanout 1 takes noticeably longer

   With only one peer contacted per round (just offset's neighbor, no second target):

   1. Round 1: infected $=\{0,1\}$
   2. Round 2: infected $=\{0,1,2,4\}$
   3. Round 3: infected $=\{0,1,2,4,5,6,7\}$
   4. Round 4: stalls — every infected node's single round-4 target already belongs to the set
   5. Round 5: node 3 finally gets reached — all 8 nodes infected

   Needing 5 rounds total to fully cover.

3. Fanout 3 (flooding) is fastest

   Contacting every neighbor every round reaches all 8 nodes in just 2 rounds — the fastest possible for this graph, at triple the per-round message cost of fanout 1.