Gossip PN-Counter Across a Cluster - The Counter

                      TASK
                    

Implementation

To replicate the PN-Counter across a cluster, each node periodically gossips its full state to random peers. This is an anti-entropy protocol that guarantees eventual convergence.

Gossip protocol:

Every 100ms, select 2 random peers from the node list
Send your full counter state (P vector + N vector) to those peers
When you receive a gossip message, merge the received state with your local state

Convergence measurement:

Apply 1000 random increments across 5 nodes
Measure the time from the last increment until all 5 nodes agree on the value
Expected convergence: within a few gossip rounds (< 1 second with 100ms interval)

Request:  {"type": "gossip_status", "msg_id": 1}
Response: {"type": "gossip_status_ok", "in_reply_to": 1, "local_value": 1000, "gossip_rounds": 42, "peers_synced": 4, "convergence_ms": 350}

Sample Test Cases

Gossip replicates counter stateTimeout: 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":1}}
{"src":"c1","dest":"n1","body":{"type":"gossip_status","msg_id":3}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}

Remote increments are visible after gossipTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1","n2"]}}
{"src":"n2","dest":"n1","body":{"type":"replicate","msg_id":2,"p_counters":{"n1":0,"n2":10},"n_counters":{"n1":0,"n2":0}}}
{"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}}

Hints

Hint 1▾

Each node gossips its full counter state (P and N vectors) to 2 random peers

Hint 2▾

Gossip interval: every 100ms, select 2 random peers and send your state

Hint 3▾

On receiving gossip: merge the received state with your local state

Hint 4▾

After 1000 increments across 5 nodes, measure time until all nodes converge

Hint 5▾

Convergence = all nodes report the same value for read()

Resources

Gossip Protocols

Demers et al. - Epidemic algorithms for replicated database maintenance

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

gossip protocolcounter replicationconvergence timeanti-entropyrandom peer selection

main.py

python