Implement Vector Clocks - The Identifier | Build Distributed Systems

                      TASK
                    

Implementation

Vector clocks solve the limitation of Lamport clocks: they can detect concurrent events. Each node maintains a vector of N counters (one per node). The rules are:

On local event or send: increment your own slot in the vector
On receive: take element-wise max of local and received vectors, then increment your own slot

Two events are concurrent if neither vector dominates the other: A || B when A[i] > B[i] for some i, and A[j] < B[j] for some j.

Implement a vc_tick handler:

Request:  {"type": "vc_tick", "msg_id": 1}
Response: {"type": "vc_tick_ok", "in_reply_to": 1, "vector": {"n1": 1, "n2": 0}}

And a vc_receive handler that merges an incoming vector:

Request:  {"type": "vc_receive", "msg_id": 2, "vector": {"n1": 0, "n2": 3}}
Response: {"type": "vc_receive_ok", "in_reply_to": 2, "vector": {"n1": 2, "n2": 3}}

Sample Test Cases

Tick increments own slotTimeout: 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":"vc_tick","msg_id":2}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "vc_tick_ok", "vector": {"n1": 1, "n2": 0}, "in_reply_to": 2, "msg_id": 1}}

Merge takes element-wise max and increments ownTimeout: 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":"vc_tick","msg_id":2}}
{"src":"n2","dest":"n1","body":{"type":"vc_receive","msg_id":3,"vector":{"n1":0,"n2":5}}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "vc_tick_ok", "vector": {"n1": 1, "n2": 0}, "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "n2", "body": {"type": "vc_receive_ok", "vector": {"n1": 2, "n2": 5}, "in_reply_to": 3, "msg_id": 2}}

Hints

Hint 1▾

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

Hint 2▾

On local event or send: increment your own slot

Hint 3▾

On receive: element-wise max, then increment your own slot

Hint 4▾

Vector clocks can distinguish concurrent events from causal ones

Hint 5▾

Initialize the vector with zeros for all known node IDs

Resources

Vector Clocks Revisited

Riak documentation on practical use of vector clocks

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

vector clockcausality trackingelement-wise maxconcurrent detection

main.py

python

#!/usr/bin/env python3
import sys
import json
class VectorClock:
    def __init__(self, node_id, all_nodes):
        self.node_id = node_id
        self.vector = {n: 0 for n in all_nodes}
    def tick(self):
        # TODO: Increment own slot, return copy of vector
        pass
    def merge(self, other_vector):
        # TODO: Element-wise max, then increment own slot
        pass
    def get(self):
        return dict(self.vector)
class Node:
    def __init__(self):
        self.node_id = None
        self.node_ids = []
        self.next_msg_id = 0
        self.vc = None
    def send(self, dest, body):
        body["msg_id"] = self.next_msg_id
        self.next_msg_id += 1
        msg = {"src": self.node_id, "dest": dest, "body": body}
        print(json.dumps(msg), flush=True)
    def reply(self, request, body):
        body["in_reply_to"] = request["body"]["msg_id"]
        self.send(request["src"], body)
def main():
    node = Node()
    for line in sys.stdin: