TASK
Implementation
Network partitions split the cluster into isolated groups. After the partition heals, gossip must merge the diverged states. Your task is to simulate this.
Implement:
partition- Block messages to specified nodesheal- Unblock all nodespartition_status- Report current partition state
Request: {"type": "partition", "msg_id": 1, "blocked": ["n3", "n4"]}
Response: {"type": "partition_ok", "in_reply_to": 1}
Request: {"type": "heal", "msg_id": 2}
Response: {"type": "heal_ok", "in_reply_to": 2}
Request: {"type": "partition_status", "msg_id": 3}
Response: {"type": "partition_status_ok", "in_reply_to": 3, "blocked": [], "is_partitioned": false, "messages_dropped": 5}Sample Test Cases
Partition blocks specified nodesTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2"]}}
{"src":"c1","dest":"n1","body":{"type":"partition","msg_id":2,"blocked":["n2"]}}
{"src":"c1","dest":"n1","body":{"type":"partition_status","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": "partition_ok", "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "partition_status_ok", "blocked": ["n2"], "is_partitioned": true, "messages_dropped": 0, "in_reply_to": 3, "msg_id": 2}}
Heal removes all blocksTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2"]}}
{"src":"c1","dest":"n1","body":{"type":"partition","msg_id":2,"blocked":["n2"]}}
{"src":"c1","dest":"n1","body":{"type":"heal","msg_id":3}}
{"src":"c1","dest":"n1","body":{"type":"partition_status","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": "partition_ok", "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "heal_ok", "in_reply_to": 3, "msg_id": 2}}
{"src": "n1", "dest": "c1", "body": {"type": "partition_status_ok", "blocked": [], "is_partitioned": false, "messages_dropped": 0, "in_reply_to": 4, "msg_id": 3}}
Hints
Hint 1▾
A partition blocks all messages between two groups of nodes
Hint 2▾
Each side continues to gossip internally
Hint 3▾
On healing, cross-partition gossip resumes and states converge
Hint 4▾
Track time-to-convergence after partition heals
Hint 5▾
Implement partition as a blocked-destinations set
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
network partitionpartition healingconvergencesplit brain
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.blocked = set()
self.messages_dropped = 0
self.neighbors = []
def send(self, dest, body):
if dest in self.blocked:
self.messages_dropped += 1
return
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 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"]