TASK
Implementation
Random gossip wastes messages because nodes may receive duplicates. A spanning tree ensures each node receives exactly one copy: the root broadcasts to its children, who forward to their children, etc.
Your task is to implement tree-based broadcast:
- Use the
topologymessage to learn your tree neighbors - On
broadcast, forward to all tree neighbors except the source - Track the forwarding path for debugging
Handle these message types:
topology: Store the neighbor list for this nodebroadcast: Store value and forward to tree neighborsread: Return all known valuestree_info: Return current tree structure for this node
Request: {"type": "tree_info", "msg_id": 1}
Response: {"type": "tree_info_ok", "in_reply_to": 1, "neighbors": ["n2", "n3"], "message_count": 5}Sample Test Cases
Topology stores neighborsTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3"]}}
{"src":"c1","dest":"n1","body":{"type":"topology","msg_id":2,"topology":{"n1":["n2","n3"],"n2":["n1"],"n3":["n1"]}}}
{"src":"c1","dest":"n1","body":{"type":"tree_info","msg_id":3}}
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": "tree_info_ok", "neighbors": ["n2", "n3"], "message_count": 0, "in_reply_to": 3, "msg_id": 2}}
Broadcast stores and reads backTimeout: 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":"read","msg_id":4}}
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": "read_ok", "messages": [42], "in_reply_to": 4, "msg_id": 3}}
Hints
Hint 1▾
Build a spanning tree from the topology provided by Maelstrom
Hint 2▾
Each node only forwards to its children in the tree
Hint 3▾
Tree broadcast has O(N-1) messages vs O(N*K) for random gossip
Hint 4▾
The root receives the broadcast and pushes down the tree
Hint 5▾
Use the topology message to learn your neighbors
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
spanning treetree broadcastoverlay networkmessage forwarding
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/usr/bin/env python3
import sys
import json
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.messages = set()
self.neighbors = []
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 forward(self, value, exclude):
# TODO: Forward value to all neighbors except exclude
pass
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":