TASK
Implementation
A Grow-only Set (G-Set) is the simplest CRDT. Elements can be added but never removed. Merge is set union, which is commutative, associative, and idempotent - guaranteeing eventual consistency via gossip.
Implement a G-Set replicated via gossip:
add- Add an element to the setread- Return all elementsmerge- Merge a remote G-Set (union)
Request: {"type": "add", "msg_id": 1, "element": "x"}
Response: {"type": "add_ok", "in_reply_to": 1}
Request: {"type": "merge", "msg_id": 2, "elements": ["a","b","c"]}
Response: {"type": "merge_ok", "in_reply_to": 2, "new_count": 2}
Request: {"type": "read", "msg_id": 3}
Response: {"type": "read_ok", "in_reply_to": 3, "elements": ["a","b","c","x"]}Sample Test Cases
Add and 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}}
Merge adds new elementsTimeout: 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":"a"}}
{"src":"n2","dest":"n1","body":{"type":"merge","msg_id":3,"elements":["a","b","c"]}}
{"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": "n2", "body": {"type": "merge_ok", "new_count": 2, "in_reply_to": 3, "msg_id": 2}}
{"src": "n1", "dest": "c1", "body": {"type": "read_ok", "elements": ["a", "b", "c"], "in_reply_to": 4, "msg_id": 3}}
Hints
Hint 1▾
A G-Set only supports add operations, never remove
Hint 2▾
Merge is simply set union: merged = local | remote
Hint 3▾
Union is commutative, associative, and idempotent - perfect for gossip
Hint 4▾
Convergence is guaranteed because sets only grow
Hint 5▾
This is the simplest CRDT to implement
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
G-SetCRDTset unioneventual consistency
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 GSet:
def __init__(self):
self.elements = set()
def add(self, elem):
self.elements.add(elem)
def merge(self, remote_elements):
new = set(remote_elements) - self.elements
self.elements.update(remote_elements)
return len(new)
def read(self):
return sorted(list(self.elements))
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.gset = GSet()
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)
body = msg["body"]
t = body["type"]
if t == "init":