Implement Hybrid Tree and Gossip Broadcast - The Gossiper

                      TASK
                    

Implementation

Pure tree broadcast is fast but fragile. Pure gossip is reliable but slow and wasteful. A hybrid approach uses tree for the first hop (fast, efficient) and gossip for reliability (catch stragglers).

Implement a hybrid broadcast:

On broadcast, forward via tree neighbors immediately
Periodically gossip all known messages to random peers (catch-up)
Track delivery path for each message (tree vs gossip)

Request:  {"type": "delivery_info", "msg_id": 1, "value": 42}
Response: {"type": "delivery_info_ok", "in_reply_to": 1, "value": 42, "delivered_via": "tree", "hops": 1}

Request:  {"type": "hybrid_stats", "msg_id": 2}
Response: {"type": "hybrid_stats_ok", "in_reply_to": 2, "tree_deliveries": 8, "gossip_deliveries": 2, "total": 10}

Sample Test Cases

Broadcast via tree tracks deliveryTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"topology","msg_id":2,"topology":{"n1":[]}}}
{"src":"c1","dest":"n1","body":{"type":"broadcast","msg_id":3,"message":42}}
{"src":"c1","dest":"n1","body":{"type":"delivery_info","msg_id":4,"value":42}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "topology_ok", "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "broadcast_ok", "in_reply_to": 3, "msg_id": 2}}
{"src": "n1", "dest": "c1", "body": {"type": "delivery_info_ok", "value": 42, "delivered_via": "tree", "hops": 0, "in_reply_to": 4, "msg_id": 3}}

Hybrid stats with zero messagesTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"hybrid_stats","msg_id":2}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "hybrid_stats_ok", "tree_deliveries": 0, "gossip_deliveries": 0, "total": 0, "in_reply_to": 2, "msg_id": 1}}

Hints

Hint 1▾

First hop uses the tree for fast delivery (low latency)

Hint 2▾

Background gossip rounds catch any missed nodes (high reliability)

Hint 3▾

Track whether each message was delivered via tree or gossip

Hint 4▾

Compare convergence speed of pure tree, pure gossip, and hybrid

Hint 5▾

The hybrid approach gives the best of both worlds

Resources

Plumtree: Epidemic Broadcast Trees

Paper on combining tree and gossip for efficient broadcast

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

hybrid broadcasttree overlaygossip fallbackconvergence speed

main.py

python

#!/usr/bin/env python3
import sys
import json
import random
class Node:
    def __init__(self):
        self.node_id = None
        self.node_ids = []
        self.next_msg_id = 0
        self.messages = {}  # value -> {via, hops}
        self.neighbors = []
        self.tree_deliveries = 0
        self.gossip_deliveries = 0
    def send(self, dest, body):
        body["msg_id"] = self.next_msg_id
        self.next_msg_id += 1
        msg = {"src": self.node_id, "dest": dest, "body": body}
        print(json.dumps(msg), flush=True)
    def reply(self, request, body):
        body["in_reply_to"] = request["body"]["msg_id"]
        self.send(request["src"], body)
def main():
    node = Node()
    for line in sys.stdin:
        line = line.strip()
        if not line:
            continue
        message = json.loads(line)
        body = message["body"]
        msg_type = body["type"]
        if msg_type == "init":
            node.node_id = body["node_id"]
            node.node_ids = body["node_ids"]
            node.reply(message, {"type": "init_ok"})
        elif msg_type == "topology":
            node.neighbors = body.get("topology", {}).get(node.node_id, [])