TASK
Implementation
Implement a broadcast system where messages sent to any node eventually reach all nodes.
Handle three message types:
- topology: Tells you your neighbors in the cluster topology
- broadcast: Contains a message value to propagate
- read: Returns all messages this node has seen
When you receive a broadcast, store the message and forward it to your neighbors. A read request should return all unique messages received so far.
Sample Test Cases
Basic broadcast with readTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c0","dest":"n1","body":{"type":"topology","msg_id":2,"topology":{"n1":[]}}}
{"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": "c1", "body": {"type": "read_ok", "messages": [100], "in_reply_to": 4, "msg_id": 3}}
Broadcast multiple messagesTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c0","dest":"n1","body":{"type":"topology","msg_id":2,"topology":{"n1":[]}}}
{"src":"c1","dest":"n1","body":{"type":"broadcast","msg_id":3,"message":"msg1"}}
{"src":"c2","dest":"n1","body":{"type":"broadcast","msg_id":4,"message":"msg2"}}
{"src":"c3","dest":"n1","body":{"type":"read","msg_id":5}}
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": "c2", "body": {"type": "broadcast_ok", "in_reply_to": 4, "msg_id": 3}}
{"src": "n1", "dest": "c3", "body": {"type": "read_ok", "messages": ["msg1", "msg2"], "in_reply_to": 5, "msg_id": 4}}
Hints
Hint 1▾
Store received messages in a set
Hint 2▾
Forward new messages to all known nodes
Hint 3▾
Handle the topology message to learn neighbors
OVERVIEW
Theoretical Hub
Broadcast Protocols
Broadcast is the foundation of many distributed algorithms. When one node learns something, it must share that knowledge with the cluster. The challenge is doing this efficiently without creating message storms.
Flooding
The simplest approach is flooding: forward every message to all neighbors. This guarantees delivery but creates O(n*m) messages for n nodes and m values. We will optimize this in later tasks.
Key Concepts
broadcastfloodingmessage propagation
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
#!/usr/bin/env python3
import sys
import json
import threading
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.neighbors = []
self.messages = set()
self.lock = threading.Lock()
self.output_lock = threading.Lock()
def send(self, dest, body):
with self.lock:
body["msg_id"] = self.next_msg_id
self.next_msg_id += 1
message = {"src": self.node_id, "dest": dest, "body": body}
with self.output_lock:
print(json.dumps(message), flush=True)
def reply(self, request, body):
body["in_reply_to"] = request["body"]["msg_id"]
self.send(request["src"], body)
def broadcast_to_neighbors(self, value, exclude=None):
# TODO: Send broadcast to all neighbors except sender
pass
def main():
node = Node()
for line in sys.stdin:
message = json.loads(line)