TASK
Implementation
Gossip protocols spread information probabilistically: instead of broadcasting to all nodes, each node forwards to K random peers. This is more resilient than tree-based broadcast because there is no single point of failure.
Your task is to implement gossip fanout:
- Maintain a set of known messages (seen set)
- On receiving a
broadcastmessage, add the value to the seen set - Forward (gossip) the value to K random peers (default K=2)
- On receiving a
readmessage, return all known values - Track gossip statistics
Broadcast: {"type": "broadcast", "msg_id": 1, "message": 42}
Response: {"type": "broadcast_ok", "in_reply_to": 1}
Read: {"type": "read", "msg_id": 2}
Response: {"type": "read_ok", "in_reply_to": 2, "messages": [42]}Sample Test Cases
Broadcast stores value and replies okTimeout: 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":"broadcast","msg_id":2,"message":42}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Read returns stored 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":"broadcast","msg_id":2,"message":10}}
{"src":"c1","dest":"n1","body":{"type":"broadcast","msg_id":3,"message":20}}
{"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": "broadcast_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": [10, 20], "in_reply_to": 4, "msg_id": 3}}
Hints
Hint 1▾
Pick K random peers from the cluster on each gossip round
Hint 2▾
Do not gossip to yourself or to the message source
Hint 3▾
Start with fanout K=2 for reasonable coverage
Hint 4▾
Use random.sample to select peers without replacement
Hint 5▾
Track which messages you have already seen to avoid re-gossip
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
gossip protocolfanoutrandom peer selectionprobabilistic broadcast
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
import random
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.messages = set()
self.fanout = 2
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 gossip(self, value, exclude=None):
# TODO: Pick K random peers and send them the value
# Exclude self and the source node
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"]