TASK
Implementation
Implement a G-Counter CRDT where each node maintains its own counter. The total is the sum of all per-node counters. Merging is done by taking the maximum of each nodes counter.
Sample Test Cases
G-Counter basicTimeout: 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":"add","msg_id":2,"delta":3}}
{"src":"c2","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": "c2", "body": {"type": "read_ok", "value": 3, "in_reply_to": 3, "msg_id": 2}}
Hints
Hint 1▾
Each node maintains its own counter
Hint 2▾
Merge by taking max of each nodes counter
Hint 3▾
Sum all counters for total
OVERVIEW
Theoretical Hub
CRDTs
Conflict-free Replicated Data Types are data structures designed for distributed systems. They guarantee convergence: all replicas that have seen the same updates will have the same state, regardless of update order.
G-Counter
A G-Counter maintains a vector of counts, one per node. To increment, a node increments only its own entry. The total value is the sum of all entries. Merge takes the component-wise maximum.
Key Concepts
CRDTG-Counterconvergence
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
#!/usr/bin/env python3
import sys
import json
class GCounter:
def __init__(self, node_id):
self.node_id = node_id
self.counts = {} # node_id -> count
def increment(self, delta=1):
# TODO: Increment this node's counter
pass
def value(self):
# TODO: Return sum of all counters
pass
def merge(self, other_counts):
# TODO: Merge by taking max of each counter
pass
if __name__ == "__main__":
pass