TASK
Implementation
Build CRDTs for conflict-free replication: G-Counter (grow-only counter), G-Set, OR-Set.
Sample Test Cases
G-Counter increment and mergeTimeout: 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":"gcounter_increment","msg_id":2}}
{"src":"c2","dest":"n2","body":{"type":"gcounter_increment","msg_id":3}}
{"src":"c3","dest":"n1","body":{"type":"gcounter_value","msg_id":4}}
Expected Output
(no output)
Hints
Hint 1▾
Merge must be commutative, associative, idempotent
Hint 2▾
G-Counter: only increment
Hint 3▾
OR-Set: add wins over remove
OVERVIEW
Theoretical Hub
CRDTs
Conflict-free Replicated Data Types allow concurrent updates that merge without conflicts. Merge is associative, commutative, idempotent.
Key Concepts
CRDTeventual consistencyconflict-free
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 uuid
class GCounter:
def __init__(self, node_id):
self.node_id = node_id
self.counts = {} # node -> count
def increment(self):
# TODO: Increment this node's count
pass
def value(self):
# TODO: Return sum of all counts
pass
def merge(self, other):
# TODO: Take max of each node's count
pass
class ORSet:
def __init__(self, node_id):
self.node_id = node_id
self.adds = {} # element -> set of tags
self.removes = set() # tags
def add(self, element):
# TODO: Add with unique tag
pass
def remove(self, element):
# TODO: Add all current tags to removes
pass
def contains(self, element):
# TODO: Element in set if any tag not removed
pass
def merge(self, other):
# TODO: Merge adds and removes