Back
+20 XP
Concept

Gossip Protocols & Epidemic Information Dissemination

In large-scale clusters, centralized broadcast trees collapse under packet storms. Gossip (epidemic) protocols have each node periodically share state with a random peer, achieving exponential $O(\log N)$ cluster convergence without single points of failure 🗣️🌐.

python
import random

class GossipNode:
    def __init__(self, name):
        self.name = name
        self.heartbeats = {name: 0}

    def tick(self):
        self.heartbeats[self.name] += 1

    def exchange(self, peer):
        # Push-Pull anti-entropy exchange:
        for k, v in peer.heartbeats.items():
            self.heartbeats[k] = max(self.heartbeats.get(k, 0), v)
        for k, v in self.heartbeats.items():
            peer.heartbeats[k] = max(peer.heartbeats.get(k, 0), v)

cluster = [GossipNode(f"Worker_{i}") for i in range(4)]
cluster[0].tick() # Event on Worker_0

# Epidemic spread:
cluster[0].exchange(cluster[1])
cluster[1].exchange(cluster[2])
print(f"Worker 2 learned state: {cluster[2].heartbeats} 🚀")

# 37. Gossip Protocols & Epidemic Information Dissemination When running 5,000 microservices across multiple AWS availability zones, having one master server ping every single machine for health checks creates a massive network choke-point and single point of failure 🛑. ```python # Centralized Heartbeat: # 5,000 nodes * 1 ping/sec = 5,000 req/sec hitting one master # If master restarts -> entire cluster goes blind! ``` ### The Epidemic Dissemination Mechanism 1. **Periodic Anti-Entropy**: Every $\Delta t$ milliseconds, a node randomly selects $k$ peers from its membership table. 2. **Push-Pull Exchange**: Nodes trade state digests (e.g. heartbeat sequence numbers, node status `ALIVE`, `SUSPECT`, `DEAD`). 3. **Logarithmic Diffusion**: Just like an epidemic spreading through a population, the number of informed nodes doubles exponentially in each round. Within $O(\log N)$ steps, all nodes converge on the exact same cluster topology 🗣️. --- ### Interactive Pop-Quiz 🧠 #### What is the computational and network complexity required for a message to reach all $N$ nodes in an epidemic gossip protocol? - [ ] $O(\log N)$ rounds of peer gossip exchanges 🌐 - [ ] $O(N^3)$ network broadcast steps - [ ] $O(1)$ instantaneous packet synchronization - [ ] $O(N!)$ combinatorial route calculations --- ### Practical Challenge 🎯 Implement `GossipNode` with `tick()` and `exchange(peer)`. Create 4 nodes. Node 0 calls `tick()` twice. Run 3 rounds where every node exchanges state with a neighbor (deterministic circular ring: 0 with 1, 1 with 2, 2 with 3, 3 with 0). Verify all nodes know Node 0 has count 2, and print `'CONVERGED'`. <details> <summary>Solution</summary> ```python class GossipNode: def __init__(self, name): self.name = name self.heartbeats = {name: 0} def tick(self): self.heartbeats[self.name] += 1 def exchange(self, peer): for k, v in peer.heartbeats.items(): self.heartbeats[k] = max(self.heartbeats.get(k, 0), v) for k, v in self.heartbeats.items(): peer.heartbeats[k] = max(peer.heartbeats.get(k, 0), v) nodes = [GossipNode(f"N{i}") for i in range(4)] nodes[0].tick() nodes[0].tick() for _ in range(3): for i in range(4): nodes[i].exchange(nodes[(i + 1) % 4]) assert all(n.heartbeats.get("N0") == 2 for n in nodes) print("CONVERGED") ``` </details>

Checkpoint

What is the computational and network complexity required for a message to reach all $N$ nodes in an epidemic gossip protocol? 🧠

Practice

Implement `GossipNode` with `tick()` and `exchange(peer)`. Create 4 nodes. Node 0 calls `tick()` twice. Run 3 rounds where every node exchanges state with a neighbor (deterministic circular ring: 0 with 1, 1 with 2, 2 with 3, 3 with 0). Verify all nodes know Node 0 has count 2, and print `'CONVERGED'`. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks