Implement Vector Clocks - The Timekeeper | Build Distributed Systems

                      TASK
                    

Implementation

Vector clocks extend Lamport clocks by maintaining a vector of N integers (one per node) instead of a single counter. This lets you determine causal relationships between events across nodes.

Rules:

Local event: increment own slot: vc[self] += 1
Send: increment own slot, attach full vector to message
Receive: vc[i] = max(vc[i], msg_vc[i]) for all i, then increment own slot

Implement vector clock handlers:

Request:  {"type": "tick", "msg_id": 1}
Response: {"type": "tick_ok", "in_reply_to": 1, "clock": [1, 0, 0]}

Request:  {"type": "send_msg", "msg_id": 2, "dest": "n2", "payload": "hello"}
Response: {"type": "send_msg_ok", "in_reply_to": 2, "clock": [2, 0, 0]}

Request:  {"type": "recv_msg", "msg_id": 3, "from": "n2", "remote_clock": [0, 5, 0], "payload": "hi"}
Response: {"type": "recv_msg_ok", "in_reply_to": 3, "clock": [3, 5, 0]}

Request:  {"type": "get_clock", "msg_id": 4}
Response: {"type": "get_clock_ok", "in_reply_to": 4, "clock": [3, 5, 0]}

Sample Test Cases

Tick increments own slot onlyTimeout: 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":"tick","msg_id":2}}
{"src":"c1","dest":"n1","body":{"type":"tick","msg_id":3}}
{"src":"c1","dest":"n1","body":{"type":"get_clock","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": "tick_ok", "in_reply_to": 2, "clock": [1, 0, 0], "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "tick_ok", "in_reply_to": 3, "clock": [2, 0, 0], "msg_id": 2}}
{"src": "n1", "dest": "c1", "body": {"type": "get_clock_ok", "in_reply_to": 4, "clock": [2, 0, 0], "msg_id": 3}}

Receive merges vectors via element-wise maxTimeout: 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":"tick","msg_id":2}}
{"src":"n2","dest":"n1","body":{"type":"recv_msg","msg_id":3,"from":"n2","remote_clock":[0,7],"payload":"hi"}}
{"src":"c1","dest":"n1","body":{"type":"get_clock","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": "tick_ok", "in_reply_to": 2, "clock": [1, 0], "msg_id": 1}}
{"src": "n1", "dest": "n2", "body": {"type": "recv_msg_ok", "in_reply_to": 3, "clock": [2, 7], "msg_id": 2}}
{"src": "n1", "dest": "c1", "body": {"type": "get_clock_ok", "in_reply_to": 4, "clock": [2, 7], "msg_id": 3}}

Hints

Hint 1▾

Each node maintains a vector of N integers, one slot per node in the cluster

Hint 2▾

On any local event: increment your own slot

Hint 3▾

On send: increment your own slot, attach the full vector to the message

Hint 4▾

On receive: take element-wise max of local and received vectors, then increment own slot

Hint 5▾

Initialize all slots to 0 on startup

Resources

Vector Clocks - Why It Is Hard to Tell the Time

Practical explanation of vector clocks with real-world examples

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

vector clockcausal orderingpartial orderdistributed time

main.py

python