Gossip Protocol

Gossip is a class of peer-to-peer information dissemination methods: nodes periodically select a small number of peers to exchange state, allowing updates to spread through multiple local interactions. It reduces reliance on a fixed broadcast center, but nodes will not see exactly the same information at the same time.

Therefore, Gossip is suitable for disseminating membership, state summaries, or convergent updates; it cannot alone authorize a unique leader or guarantee that all nodes process commands in the same order. Dissemination and consensus solve different problems.

Do not mix the two sets of classifications

Push, Pull, and Push-Pull describe the direction of information flow; Rumor Mongering and Anti-Entropy describe propagation and reconciliation strategies. These are two composable dimensions.

Rumor mongering typically propagates a new update a limited number of times and then stops, to control costs; Anti-Entropy periodically compares states to recover accidentally missed updates. A single Pull catches up only if the peer has all the required data, the transmission succeeds, and capacity is sufficient.

Why early propagation is fast

In an idealized model, nodes that know an update continue to contact unknown nodes, and the coverage count can grow rapidly in the early stages of propagation. Later, however, it will increasingly select nodes that are already known, leaving a small number of nodes as the coverage tail.

Under assumptions of good random mixing and sufficient message capacity, the propagation time of many epidemic protocols grows approximately logarithmically with the number of nodes. This is a conclusion with probabilities and model conditions; not any network can reach all nodes in exactly log₂N rounds.

If the connection between two data centers is broken, local diffusion cannot cross the partition no matter how fast it is. If the rate of update generation exceeds the available propagation bandwidth, backlogs may also continue to grow. Efficient Reconciliation and Flow Control directly discusses the constraints of anti-entropy under limited capacity.

Four nodes, two informed: the next round may not cover all

Assume that at the start of the synchronous round, only 0 and 1 know the update. Each informed node selects a target from the other three nodes with equal probability to push, and all messages are delivered. Newly informed nodes forward only in the next round. The two senders have 3×3=9 equally likely choices, which can be enumerated directly:

from itertools import product
from fractions import Fraction

known = {0, 1}
outcomes = [known | {target0, target1}
            for target0, target1 in product((1, 2, 3), (0, 2, 3))]
assert len(outcomes) == 9
assert sum(len(result) == 4 for result in outcomes) == 2
assert sum(len(result) == 2 for result in outcomes) == 1
expected_new = Fraction(sum(len(result) - 2 for result in outcomes), 9)
assert expected_new == Fraction(10, 9)

# For a node that is not yet informed, the probability that each sender does not select it is 2/3.
assert expected_new == 2 * (1 - Fraction(2, 3)**2)

Only 0→2,1→3 and 0→3,1→2 can cover all four nodes, with a probability of 2/9; 0→1,1→0 adds no new coverage at all, with a probability of 1/9. The remaining choices only add one informed node. The average new coverage is 10/9, not the two required by mechanical doubling.

Generalizing to N nodes and k informed nodes, under the conditions of independent uniform selection and no packet loss, the expected new coverage in the next round is (N−k)×[1−(1−1/(N−1))^k]. This is the expectation for one round, not for any actual propagation trajectory. Network partitions, bias towards local selection, or insufficient message capacity will all change this model.

Limited propagation times also leave probabilistic omissions. For example, if A passes the update to B and then stops, and B's only choice is to select A again, C and D will never receive this rumor. The significance of periodic anti-entropy is to provide subsequent reconciliation opportunities; if the update itself has been completely discarded, subsequent contacts will not recover the content no matter how frequent they are.

Two informed nodes need not become four next round

Derive the expectation for one uninformed node: one sender misses it with probability 1−1/(N−1); k independent senders all miss with that probability raised to k. Take the complement and sum over N−k uninformed nodes. Those nodes’ outcomes need not be independent: linearity of expectation is enough.

$$E[\Delta ]=(N-k)\left[1-{\left(1-\frac{1}{N-1}\right)}^k\right]$$

Deduplication, versions, and merging determine the final state

The same update may arrive multiple times via different paths. The receiver needs stable identifiers or versioning rules to avoid executing side effects repeatedly. If complete state is propagated, you need to define how to merge two states; if operations are propagated, you need to consider loss, duplication, and ordering.

For example, if each node maintains its own monotonic counter component, and upon receiving another copy's state, takes the maximum value for each component and then sums them, you can avoid duplicate messages causing the counter to be accumulated repeatedly. Directly broadcasting "add one to the total" and executing it each time it is received cannot tolerate duplicates.

Old vs. new judgment cannot rely solely on local reception time. Delayed messages may arrive later than newer ones; if a member restarts and resets its counter to zero, generational information such as incarnation is needed. More general merging conditions are discussed in Conflict Resolution.

G-Counter: Exchange cumulative state per writer, do not add snapshots again

Three writers each only increment their own component. A has produced two increments, B has produced three, and C has produced one. When replicas exchange state, take the larger component for the same writer, then sum the total. Duplicate snapshots do not become new operations.

from itertools import permutations

def join(a, b):
    return {writer: max(a.get(writer, 0), b.get(writer, 0))
            for writer in a.keys() | b.keys()}

updates = [{"A": 2}, {"B": 3}, {"C": 1}]
for order in permutations(updates):
    state = {}
    for update in (*order, order[0], order[1]):  # Intentionally duplicate and change order
        state = join(state, update)
    assert state == {"A": 2, "B": 3, "C": 1}
    assert sum(state.values()) == 6
assert join({"A": 2}, {"A": 1}) == {"A": 2}  # Late old state does not regress

# Reusing identity after restart but resetting local cumulative values to zero will cause new increments to be swallowed by old components.
assert join({"A": 2}, {"A": 1}) != {"A": 3}
# New incarnation can use a new identity; old components are still retained.
assert sum(join({"A#1": 2}, {"A#2": 1}).values()) == 3

Per-component max satisfies commutativity, associativity, and idempotence, so complete state can still converge when arriving repeatedly or out of order. The prerequisite is that all increments are eventually propagated, and each writer exclusively owns its own monotonic component; if two processes mistakenly use the same identity and each increment from 0 to 1, the merge will only yield 1, failing to express two independent increments.

On restart, you can restore persistent components or use a new incarnation, but a new identity is not a cost-free fix: old components cannot be arbitrarily deleted, or the total will drop, requiring separate identity recycling or compression protocols. The G-Counter here only supports increments, not arbitrary decrements. See Akka Distributed Data for merging conditions of state-based CRDTs and GCounter examples.

Member propagation and data anti-entropy

SWIM's probe layer obtains liveness evidence, and its dissemination layer spreads join, leave, suspicion, and liveness updates. It is incomplete to only write about propagating dead events: refuting suspicions and new member joins also require dissemination. Protocol details are in SWIM.

For large-scale business data, propagating complete state item by item may be too expensive. You can first exchange summaries, then locate the ranges that need synchronization. Merkle trees are one such tool; they help reduce transmission but do not automatically resolve version conflicts. See Anti-Entropy and Data Repair for details.

Fanout, period, and payload budget

If each node contacts 3 peers per second and sends about 2 KB each time, a single node's one-way send volume is about 6 KB/s; for a thousand nodes, it is about 6 MB/s, not including replies and protocol overhead. This demonstrates an estimation method, not a default configuration for any implementation.

Increasing fanout or shortening the period may speed up propagation, but it may also cause congestion and processing queues, making actual convergence slower. You must also limit the number of retransmissions per update, message size, queue backlog, and reserve reconciliation opportunities for anti-entropy.

Failure-related updates are usually more urgent than low-priority statistics, but priority cannot cause certain categories to never be sent. Combining periodic summaries with event-driven fast propagation can balance timeliness and eventual coverage.

What Gossip cannot replace

It is a state allowed by Gossip for two nodes to temporarily hold different member lists. If they each grant exclusive write permissions based on their local lists, they may both consider themselves the sole owner. When exclusive decisions are needed, weakly consistent views should be integrated into coordination protocols with clear safety rules.

Similarly, Raft AppendEntries is part of a replicated state machine protocol and cannot be used as the definition of all reliable broadcast. When evaluating a system, you should separately write out the guarantees for propagation, ordering, persistence, and delivery, avoiding judging correctness solely based on "whether there is a leader."

References

• Efficient Reconciliation and Flow Control for Anti-Entropy Protocols
• SWIM Paper
• Failure Detection

Keywords: gossip, push, pull, push-pull, rumor mongering, anti-entropy, fanout, probabilistic coverage, state merging