Questions: Gossip Protocols and Epidemic Algorithms

Question 1

In a gossip-based distributed system with 1,000 nodes, 200 nodes suddenly crash mid-operation. What happens to information dissemination?

• A. Dissemination halts because the crashed nodes create gaps that block propagation paths
• B. The protocol must be manually reconfigured by an administrator to route around the failed nodes
• C. Dissemination slows to O(n) rounds because the remaining nodes must compensate for missing peers
• D. The remaining 800 nodes continue gossiping normally, and information still reaches all healthy nodes

Answer: (D)

Gossip's robustness comes from having no coordinator and no fixed topology. When nodes crash, the remaining nodes simply stop receiving gossip from them (enabling failure detection) but continue their own random peer selection uninterrupted. The same information travels through many independent random paths, so no single failure cuts off propagation. This is a core advantage over centralized broadcast approaches.

Question 2

Why does gossip achieve O(log n) convergence rounds rather than O(n) rounds?

• A. Each node broadcasts to all peers simultaneously, splitting the propagation work across the cluster
• B. Each gossip round roughly doubles the number of informed nodes, producing exponential growth in coverage
• C. Gossip uses a pre-built binary tree topology that guarantees logarithmic propagation depth
• D. Nodes cache and replay messages at exponentially increasing intervals to reduce redundancy

Answer: (B)

Gossip spreads like a biological epidemic: after round 1, ~2 nodes know the information; after round 2, ~4; after round 3, ~8. This doubling means all n nodes are reached in approximately log₂(n) rounds. There is no pre-built tree — the exponential behavior emerges naturally from random peer selection, just as epidemics spread through random social contacts.

Question 3

Gossip protocols can detect node failures by observing that a node's heartbeat counter stops incrementing across multiple gossip rounds.

• T. True
• F. False

Answer: True

Each node includes a heartbeat counter in its gossip state that increments with each round. If a node's counter stops updating, its peers infer that it is no longer running and mark it as suspected-failed. This passive failure detection requires no dedicated health-check infrastructure — failure detection is a natural byproduct of the same gossip mechanism used for state dissemination.

Question 4

Gossip protocols require a central coordinator node to guarantee that information eventually reaches most nodes in the cluster.

• T. True
• F. False

Answer: False

Decentralization is the defining feature of gossip. Each node independently selects random peers and exchanges state — there is no coordinator, master node, or fixed propagation tree. This is what makes gossip robust to failures: removing any single node, including one that might act as a hub, does not disrupt the protocol's eventual convergence.

Question 5

Why does random peer selection (rather than a fixed communication topology) make gossip protocols more fault-tolerant?

Model answer: With random peer selection, the same piece of information travels through many independent, overlapping paths to reach its destination. No single node or link is on the critical path — if a particular peer is unavailable in one round, the information arrives through different random connections in subsequent rounds. A fixed topology (like a tree or ring) creates single points of failure: one crashed node can cut off entire subtrees or break the propagation chain entirely.

This is also why gossip's convergence guarantee is probabilistic rather than deterministic: any single message may fail to deliver, but the protocol's redundancy ensures that the probability of all paths failing simultaneously decreases rapidly with each round.