Gossip: the cheap channel and what it may carry

What can gossip carry cheaply, and what can it never give?

Epidemic dissemination (gossip) reaches everyone in O(log N) rounds at constant fan-out (each node tells a fixed small number of peers per round), with O(N log N) total messages. The property that matters is that no node must be up. Consensus needs a majority continuously; gossip needs nobody in particular. That is the price ratio behind the split between control plane and data plane.

What gossip cannot give is order or termination: nobody knows when the dissemination is complete, and two facts may arrive in either sequence. Therefore gossip can only carry payloads whose merge is commutative, associative and idempotent: the result is the same whatever the order and however many times a fact is delivered. Examples: a max of heartbeat counters, a union of a member set, a version vector. This is not a convention. It is a precondition, and it is "the right algebra removes the coordinator" again: the algebra is what makes the coordination-free channel usable at all. Membership gossip carries "the highest heartbeat counter I have seen for each node" precisely because max is a join-semilattice operation (an operation that always yields the "least upper bound"), and therefore immune to reordering and redelivery.

The failure mode is instructive. Removal is not monotonic. A set union can never forget. So a departed node's entry must be tombstoned (marked as deleted, and the mark is kept), and the tombstone must outlive any rumour that could resurrect the entry. This has the same shape as immutable data plus indirection plus a garbage collector, with a retention parameter that must exceed the longest possible partition. It now appears in a domain with no storage in it, and it carries the same unverifiable assumption as always: that the partition was shorter than the tombstone TTL. Full membership state is also O(N) per node, which is why very large clusters use partial views instead of complete ones.

Compression: gossip trades order and termination for the absence of any required node, and can therefore carry only payloads whose merge is a semilattice join, plus tombstones with an expiry you cannot verify.