TASK
Implementation
A 2P-Set (two-phase set) supports both add and remove by maintaining two G-Sets: the add-set and the remove-set (tombstones). An element is in the set if it is in the add-set but NOT in the remove-set.
Request: {"type": "add", "msg_id": 1, "element": "x"}
Response: {"type": "add_ok", "in_reply_to": 1}
Request: {"type": "remove", "msg_id": 2, "element": "x"}
Response: {"type": "remove_ok", "in_reply_to": 2}
Request: {"type": "read", "msg_id": 3}
Response: {"type": "read_ok", "in_reply_to": 3, "elements": []}
Request: {"type": "merge", "msg_id": 4, "add_set": ["a","b"], "remove_set": ["b"]}
Response: {"type": "merge_ok", "in_reply_to": 4}Sample Test Cases
Add then readTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"add","msg_id":2,"element":"x"}}
{"src":"c1","dest":"n1","body":{"type":"read","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": "add_ok", "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "read_ok", "elements": ["x"], "in_reply_to": 3, "msg_id": 2}}
Add then remove then readTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"add","msg_id":2,"element":"y"}}
{"src":"c1","dest":"n1","body":{"type":"remove","msg_id":3,"element":"y"}}
{"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": "add_ok", "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "remove_ok", "in_reply_to": 3, "msg_id": 2}}
{"src": "n1", "dest": "c1", "body": {"type": "read_ok", "elements": [], "in_reply_to": 4, "msg_id": 3}}
Hints
Hint 1▾
A 2P-Set has two internal G-Sets: add-set and remove-set
Hint 2▾
To add: insert into add-set. To remove: insert into remove-set
Hint 3▾
Value = add-set - remove-set
Hint 4▾
Once removed, an element cannot be re-added (tombstone is permanent)
Hint 5▾
Merge both G-Sets independently via union
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
2P-SetCRDTtombstone setadd-remove semantics
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
#!/usr/bin/env python3
import sys
import json
class TwoPSet:
def __init__(self):
self.add_set = set()
self.remove_set = set()
def add(self, elem):
self.add_set.add(elem)
def remove(self, elem):
if elem in self.add_set:
self.remove_set.add(elem)
def read(self):
return sorted(list(self.add_set - self.remove_set))
def merge(self, remote_add, remote_remove):
self.add_set.update(remote_add)
self.remove_set.update(remote_remove)
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.tps = TwoPSet()
def send(self, dest, body):
body["msg_id"] = self.next_msg_id
self.next_msg_id += 1
print(json.dumps({"src": self.node_id, "dest": dest, "body": body}),
flush=True)
def reply(self, req, body):
body["in_reply_to"] = req["body"]["msg_id"]
self.send(req["src"], body)
def main():
node = Node()
for line in sys.stdin:
line = line.strip()
if not line: continue
msg = json.loads(line)