Gossip Protocol

Gossip Protocol

A Gossip Protocol (also called epidemic protocol) is a way for nodes in a distributed system to disseminate information to all other nodes — without any central coordinator. Each round, every node picks one or more random peers and exchanges state.

Why Gossip?

• Decentralized — no single point of failure.
• Scalable — information spreads logarithmically. With N nodes, it takes O(log N) rounds for all nodes to have the information.
• Fault-tolerant — nodes can fail without stopping propagation.

How It Works

Each node maintains a version number for each piece of information. When two nodes gossip:

1. Each sends its known state to the other.
2. Both update their state by taking the maximum version for each key.

function gossipRound(nodes, sourceIdx, targetIdx) {
  const source = nodes[sourceIdx];
  const target = nodes[targetIdx];

  // Merge: take max version for each key
  for (const key in source.state) {
    if (!target.state[key] || source.state[key].version > target.state[key].version) {
      target.state[key] = { ...source.state[key] };
    }
  }
  for (const key in target.state) {
    if (!source.state[key] || target.state[key].version > source.state[key].version) {
      source.state[key] = { ...target.state[key] };
    }
  }
}

Convergence

In each round, any node that knows a piece of information can spread it to one random node. The probability that after r rounds ALL nodes know the information follows the epidemic model — it spreads exponentially fast.

Real-World Uses

• Amazon DynamoDB — nodes gossip to propagate ring membership changes.
• Apache Cassandra — uses gossip for node health, schema, and token ring changes.
• Bitcoin — transactions propagate via gossip over the peer-to-peer network.
• Redis Cluster — cluster topology changes propagate via gossip.

Your Task

Implement gossipRound(nodes, sourceIdx, targetIdx) that merges state between two nodes. Each node has a state object mapping keys to { value, version } objects. Take the higher version for each key.

Also implement spreadInfo(nodes, key, value, fromIdx) that sets a value on one node and simulates 3 rounds of gossip to all other nodes sequentially.