Gossip Protocol

Randomly selecting peers and exchanging the latest information—gossip disseminates information to the entire cluster in O(log N) rounds through "chitchat". There is no leader, no consensus, and no single point of failure; the cost is temporary inconsistency of cluster state before convergence. From membership propagation to anti-entropy repair, gossip is the information superhighway of decentralized distributed systems.

Three Types of Gossip

The core of gossip is "each node periodically randomly selects a peer to exchange information." Based on the direction of information flow, they are divided into three types:

Push (Rumor Mongering)

A node has an update → actively pushes it to a random peer → the peer continues to push.

Suitable for "hot" updates (recently occurred, requiring rapid propagation). If the update is not pushed enough times (the rumor stops circulating), a fallback (anti-entropy) is needed.

Pull

A node actively pulls the latest information from a random peer. Suitable for newly joined or long-unsynchronized nodes—only one pull is needed to catch up.

Push-Pull

Both parties exchange summaries → each pulls updates that the other has but they do not. Most effective—both parties benefit, and network utilization is highest.

Epidemic Broadcast

Epidemic guarantees probabilistic reliability: after O(log N) rounds, all nodes receive the message with probability ≈ 1.

Convergence Analysis

Each round: each node randomly selects 1 peer for push-pull
Round 1: 1 node → 2 nodes know
Round 2: 2 → 4
Round 3: 4 → 8
...
Round log₂(N): all nodes know

This assumes perfect propagation (infinite bandwidth, no packet loss)
In practice: fanout = O(log N) per round → probabilistic coverage

Comparison with Reliable Broadcast

• Reliable broadcast (e.g., Raft AppendEntries): O(N) messages, deterministic reliability, requires a leader
• Epidemic gossip: O(log N) messages per node, probabilistic reliability, no leader, tolerates node failures/network partitions

Anti-Entropy + Merkle Trees

Gossip may lose messages (probabilistic). Anti-entropy fills in the gaps using full comparisons.

Merkle tree: each leaf node = hash(data block), each internal node = hash(children). Two nodes compare root hashes → if identical, data is consistent → if different, recursively compare children → locate specific inconsistent blocks → transmit only these blocks.

Advantage: identifies inconsistencies without transmitting all data. BitTorrent, Cassandra, and Dynamo all use Merkle trees for anti-entropy.

SWIM's Gossip Layer

SWIM's ping/ping-req layer is responsible for failure detection. Detection results (suspected/confirmed dead) are disseminated via gossip. This is an instance of push gossip: only rare events like suspected/dead are disseminated.

References

• Paper: "Epidemic Algorithms for Replicated Database Maintenance" (Demers et al, 1987)
• Paper: "SWIM" (Das et al, 2002 — section 4: Dissemination)

Keywords: gossip, push-pull, epidemic broadcast, anti-entropy, Merkle tree, SWIM, probabilistic reliable