Pass the Maelstrom G-Counter Workload - The Counter

                      TASK
                    

Implementation

The Maelstrom g-counter workload is the definitive correctness test for your CRDT counter implementation. It runs your nodes in a simulated distributed environment and verifies that the counter behaves correctly under concurrent operations.

Workload operations:

add: increment the counter by a delta value
read: return the current counter value

Checker properties:

Every read value must be <= the sum of all add operations (no over-counting)
The counter must be eventually consistent (all nodes converge to the same value)
The counter must be monotonically non-decreasing per node (G-Counter property)

Running the test:

maelstrom test -w g-counter --bin your_node --node-count 3 --rate 100 --time-limit 20

Request:  {"type": "add", "msg_id": 1, "delta": 5}
Response: {"type": "add_ok", "in_reply_to": 1}

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

Sample Test Cases

Add and read operationsTimeout: 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":"add","msg_id":2,"delta":5}}
{"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", "in_reply_to": 3, "value": 5, "msg_id": 2}}

Read never exceeds total addsTimeout: 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,"delta":10}}
{"src":"c1","dest":"n1","body":{"type":"add","msg_id":3,"delta":20}}
{"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": "add_ok", "in_reply_to": 3, "msg_id": 2}}
{"src": "n1", "dest": "c1", "body": {"type": "read_ok", "in_reply_to": 4, "value": 30, "msg_id": 3}}

Hints

Hint 1▾

The Maelstrom g-counter workload sends add and read operations to your nodes

Hint 2▾

Your implementation must handle: init, add (delta), read

Hint 3▾

Nodes must gossip state to ensure eventual consistency across the cluster

Hint 4▾

The checker verifies: reads never exceed the sum of all adds

Hint 5▾

Use the PN-Counter implementation from the previous task as the foundation

Resources

Maelstrom G-Counter

Maelstrom documentation on the g-counter workload

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

Maelstromg-counter workloadcorrectness verificationlinearizability checkdistributed testing

main.py

python