Implement a G-Counter (Grow-Only CRDT) - The Counter

                      TASK
                    

Implementation

A G-Counter (Grow-only Counter) is the simplest CRDT. Each node maintains a vector of N integers, one per node. A node only increments its own slot, and the total value is the sum of all slots.

Data structure: vector of N integers, where N = number of nodes.

Operations:

increment(): counters[my_node_id] += 1
value(): sum(counters)
merge(other): counters[i] = max(counters[i], other.counters[i]) for all i

Why it works: each node independently increments its own slot. The merge function (element-wise max) is commutative, associative, and idempotent — making it a valid CRDT that always converges regardless of message ordering or duplication.

Request:  {"type": "increment", "msg_id": 1}
Response: {"type": "increment_ok", "in_reply_to": 1, "local_value": 1}

Request:  {"type": "read", "msg_id": 2}
Response: {"type": "read_ok", "in_reply_to": 2, "value": 5}

Sample Test Cases

Increment increases local counterTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2","n3"]}}
{"src":"c1","dest":"n1","body":{"type":"increment","msg_id":2}}
{"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": "increment_ok", "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "read_ok", "in_reply_to": 3, "value": 1, "msg_id": 2}}

Multiple increments accumulateTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"increment","msg_id":2}}
{"src":"c1","dest":"n1","body":{"type":"increment","msg_id":3}}
{"src":"c1","dest":"n1","body":{"type":"increment","msg_id":4}}
{"src":"c1","dest":"n1","body":{"type":"read","msg_id":5}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "increment_ok", "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "increment_ok", "in_reply_to": 3, "msg_id": 2}}
{"src": "n1", "dest": "c1", "body": {"type": "increment_ok", "in_reply_to": 4, "msg_id": 3}}
{"src": "n1", "dest": "c1", "body": {"type": "read_ok", "in_reply_to": 5, "value": 3, "msg_id": 4}}

Hints

Hint 1▾

Each node maintains a vector of N integers (one slot per node)

Hint 2▾

Node I only increments its own slot: counters[I] += 1

Hint 3▾

Value = sum of all slots across the vector

Hint 4▾

Merge = element-wise max of two vectors

Hint 5▾

This guarantees convergence: merge is commutative, associative, and idempotent

Resources

CRDTs: G-Counter

CRDT glossary with G-Counter definition and properties

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

G-CounterCRDTvector of counterselement-wise maxconvergence

main.py

python