Disseminating Suspicion by Gossip: Anti-Entropy, Rumor Mongering, and Merge Order

A node that suspects a peer holds a fact that every other node needs and no node has asked for. Sending it to everyone directly costs n messages per suspicion and does not scale; sending it to one neighbour and letting the news spread costs a logarithmic number of rounds and no coordination. The gossip channel is the second option, and its correctness depends less on the spreading than on what happens when two nodes with different news meet.

Two dissemination styles and what each guarantees

Rumor mongering, also called the push style, works like an infection. A node with an update selects b random peers, sends the update, and stops sending it after some number of rounds in which nobody needed it. The update spreads fast and then dies out, and a node that was unreachable during the epidemic may never receive it.

Anti-entropy works like a comparison. Each node periodically selects a random peer and exchanges a digest of its full state, and each side pulls whatever the other has that it lacks. It is slower per round, because the digest and the reconciliation cost more than one update, but it is self-healing: a node that missed the rumor gets it on the next anti-entropy round regardless of how the rumor died.

Production membership protocols use both. The push style carries time-sensitive updates, so a suspicion reaches the cluster in a few rounds. Anti-entropy runs at a lower rate as a backstop, so a node that was partitioned or restarted converges eventually. The combination gives fast common-case propagation and eventual completeness, and the two rates are independent knobs: push frequency controls latency, anti-entropy frequency controls the tail of convergence.

Why the round count is logarithmic, and when it is not

With n nodes and b random targets per round, the number of nodes holding the update multiplies by roughly 1 + b per round while the update is rare. Starting from one holder, after r rounds the expected number of holders is (1+b)^r until saturation, so reaching n takes about log_(1+b) n rounds. With b = 3 and n = 1000, that is about five rounds; with n = 100000, about nine.

The logarithm is real but the constant matters. Each round is a network round trip, and the gossip interval sets how long a round lasts, so a membership change takes a handful of intervals to be widely known. If the interval is one second, a thousand-node cluster learns of a suspicion in roughly five seconds and a hundred-thousand-node cluster in roughly nine, which is fine. If the interval is thirty seconds, the same propagation takes minutes, and a system that needs failover within seconds cannot use that interval.

The other thing the logarithm does not capture is the fan-out cost. Each round sends b messages per holder, so the total traffic per round grows as the number of holders grows: the aggregate message count over the whole epidemic is O(n log n), not O(n). For membership traffic on a large cluster this is the dominant cost, which is why b is small and why the updates are small. It is also why designs piggyback updates on messages they were already sending, which converts the marginal cost of dissemination into zero at the price of coupling propagation latency to the rate of that other traffic, exactly as in SWIM’s probe cycle.

The merge rule has to be a total order

Gossip delivers updates out of order, more than once, and from multiple sources. The receiver needs a rule that takes any set of updates and produces the same state regardless of arrival order and duplication. That is a join over a semilattice, and it requires the update ordering to be a total order with a well-defined maximum.

For membership updates the order is the pair (incarnation, status). Two updates about the same node with different incarnations are ordered by incarnation. Two updates with the same incarnation are ordered by status, with alive above suspect above dead. The merge is max, which is commutative, associative, and idempotent, so duplicated and reordered delivery converge to the same state.

The design breaks if any two updates about the same node are incomparable. Suppose two observers both report suspect at the same incarnation for the same node. They are equal under the order, so either is accepted and the state is the same. Now suppose the status field also carried the observer’s identity, so that two suspicions at the same incarnation were distinct values. The order would no longer be total, and two nodes could hold different states forever, each believing its own suspicion. The fix is to keep the observer out of the ordering, or to make the tie broken deterministically by identifier; either way the merge must be a function of the update content alone.

type Update struct {
    Node        string
    Incarnation uint64
    Status      uint8  // alive=3, suspect=2, dead=1
}

func merge(a, b Update) Update {
    if a.Node != b.Node { panic("merge of distinct nodes") }
    if a.Incarnation != b.Incarnation {
        if a.Incarnation > b.Incarnation { return a }
        return b
    }
    if a.Status >= b.Status { return a }
    return b
}

The comparison order is not arbitrary. Putting incarnation above status is what lets a node refute a suspicion about itself, because its own increment outranks any opinion formed at a lower incarnation. Reversing the two fields would let an old alive beat a newer dead, which is precisely the resurrection bug the ordering exists to prevent.

Digests, false positives, and the cost of reconciliation

Anti-entropy needs the two sides to find their differences without shipping their full state. The standard approach is a digest: each node computes a compact summary of its membership table and sends it, and the receiver compares. A whole-table hash is cheap but useless for locating differences, because it only says whether the tables match. Per-entry hashes are precise but cost as much as the table.

The practical middle ground is to exchange the full table when it is small, which membership tables are, and to use a digest only when the table is large. A thousand-entry table with a name and a few integers per entry is on the order of tens of kilobytes, which is not worth reconciling cleverly. A hundred-thousand-entry table is a different problem and needs a Merkle-style tree or a sampled digest, with the trade that a tree costs O(log n) hashes per comparison and detects differences without listing them.

The subtlety in digest schemes is that a hash mismatch reports only that a difference exists, not which side is newer. The pull has to fetch entries and then apply the merge rule, which is why the merge rule must be order-independent: the reconciliation can fetch in any order and apply immediately, and the result is correct without a second pass.

Convergence is not agreement

The gossip layer guarantees that every node that stays reachable long enough converges to the same membership state. It does not guarantee that the state is correct, and it does not guarantee that all nodes converge at the same time. During the interval between a suspicion being raised and its dissemination completing, different nodes hold different views, and a system that reads membership during that window gets a mixed answer.

This is a genuine hazard for quorum-based protocols, because the quorum is counted against the membership view. A node that believes the cluster has five members and a node that believes it has four can disagree about whether three nodes constitute a majority. The usual resolution is that membership changes go through a consensus protocol rather than through gossip, and gossip only carries suspicion, which is advisory. That separation is why the quorum arithmetic in a consensus cluster is over a configuration that changes deliberately, while the liveness view changes continuously and approximately.

The other consequence of approximate convergence is that a node can be declared dead by a majority of observers while a minority still considers it alive, and the minority’s traffic to it keeps working. That is the asymmetric partition case, and gossip makes it visible rather than resolving it. Per-observer diagnosis is the layer that decides what to do with a set of conflicting suspicions rather than a single merged one.

Sizing the parameters

Three numbers set the behaviour: the fan-out b, the push interval, and the anti-entropy interval. Fan-out trades traffic for rounds; doubling it halves the round count and doubles the per-round messages. The push interval trades latency for background load and should be set below the failover budget divided by the expected round count. The anti-entropy interval trades convergence tail for cost and should be set so that a node offline for a typical maintenance window converges within a bounded time after returning.

The parameters interact with cluster size in a way that is easy to get wrong. A configuration tuned for a hundred nodes, with a one-second push interval and fan-out three, produces a few hundred messages per second in the background. The same configuration on ten thousand nodes produces tens of thousands of messages per second, and the gossip traffic becomes a measurable fraction of the network. Scaling up requires reducing the push rate or the fan-out, both of which lengthen detection, which is why large clusters tend to use a hierarchy rather than a flat gossip plane, as described in hierarchical heartbeat aggregation.