Build Flat Tree Topology Gossip - The Gossiper

                      TASK
                    

Implementation

Optimize your broadcast by using a tree topology. Instead of flooding to all neighbors, organize nodes into a spanning tree where each message travels along tree edges exactly once.

This reduces message complexity from O(n*m) to O(n) for each broadcast, where n is the number of nodes.

Sample Test Cases

Tree broadcast with 3 nodesTimeout: 10000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3"]}}
{"src":"c0","dest":"n1","body":{"type":"topology","msg_id":2,"topology":{"n1":["n2"],"n2":["n1","n3"],"n3":["n2"]}}}
{"src":"c1","dest":"n1","body":{"type":"broadcast","msg_id":3,"message":100}}
{"src":"c1","dest":"n1","body":{"type":"read","msg_id":4}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c0", "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": "n2", "body": {"type": "broadcast", "message": 100, "msg_id": 3}}
{"src": "n1", "dest": "c1", "body": {"type": "read_ok", "messages": [100], "in_reply_to": 4, "msg_id": 4}}

Hints

Hint 1▾

Use the provided topology to form a tree

Hint 2▾

Avoid sending back to parent

Hint 3▾

Tree ensures O(n) messages

Hint 4▾

Reply with broadcast_ok before forwarding to neighbors - this ensures deterministic msg_id ordering in the output

                      OVERVIEW
                    

Theoretical Hub

Spanning Trees

A spanning tree connects all nodes with exactly n-1 edges and no cycles. Broadcasting along a tree ensures each message is delivered exactly once to each node, minimizing network traffic.

Key Concepts

tree topologyspanning treeefficient propagation

main.py

python

#!/usr/bin/env python3
import sys
import json
import threading
class Node:
    def __init__(self):
        self.node_id = None
        self.neighbors = []
        self.messages = set()
        self.lock = threading.Lock()
        # TODO: Implement tree-based broadcast
def main():
    node = Node()
    # TODO: Use topology to build efficient broadcast tree
    pass
if __name__ == "__main__":
    main()