TASK
Implementation
Instead of only gossiping when a new broadcast arrives, add periodic gossip rounds: every interval, pick K random peers and send them all your known messages. This ensures convergence even if messages are dropped.
Implement a gossip_round handler that triggers a single gossip round:
Request: {"type": "gossip_round", "msg_id": 1}
Response: {"type": "gossip_round_ok", "in_reply_to": 1, "peers_contacted": 2, "messages_sent": 5}And a gossip_sync handler that receives a full state from a peer:
Request: {"type": "gossip_sync", "msg_id": 1, "messages": [1, 2, 3]}
Response: {"type": "gossip_sync_ok", "in_reply_to": 1, "new_count": 2}The sync handler merges the received messages with the local set and reports how many were new.
Sample Test Cases
Gossip round with no messages sends nothingTimeout: 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":"gossip_round","msg_id":2}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Gossip sync merges new 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":"n2","dest":"n1","body":{"type":"gossip_sync","msg_id":3,"messages":[10,20,30]}}
{"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": "n2", "body": {"type": "gossip_sync_ok", "new_count": 2, "in_reply_to": 3, "msg_id": 2}}
{"src": "n1", "dest": "c1", "body": {"type": "read_ok", "messages": [10, 20, 30], "in_reply_to": 4, "msg_id": 3}}
Hints
Hint 1▾
Push gossip sends on broadcast; pull gossip syncs periodically
Hint 2▾
A gossip round checks all known messages against a random peer
Hint 3▾
Track convergence: how many rounds until all nodes have all messages
Hint 4▾
The timer interval affects latency vs message overhead tradeoff
Hint 5▾
Implement gossip_round as a message type triggered externally for testing
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
periodic gossipconvergence timeanti-entropypull gossip
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 do_gossip_round(self):
# TODO: Pick K random peers, send them all known messages
# Return (peers_contacted, total_messages_sent)
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"]