Implement Happens-Before and Concurrency Detection - The Timekeeper

                      TASK
                    

Implementation

Vector clocks let you determine the causal relationship between any two events. Given two vector clock stamps a and b:

a happens-before b (a -> b): every element of a <= b AND at least one element of a < b
b happens-before a (b -> a): every element of b <= a AND at least one element of b < a
concurrent (a || b): neither happens-before the other (some elements of a are greater, some of b are greater)

Implement a compare handler:

Request:  {"type": "compare", "msg_id": 1, "clock_a": [2, 3, 1], "clock_b": [2, 4, 2]}
Response: {"type": "compare_ok", "in_reply_to": 1, "result": "A_BEFORE_B"}

Request:  {"type": "compare", "msg_id": 2, "clock_a": [3, 1, 0], "clock_b": [1, 3, 0]}
Response: {"type": "compare_ok", "in_reply_to": 2, "result": "CONCURRENT"}

Request:  {"type": "compare", "msg_id": 3, "clock_a": [5, 3, 2], "clock_b": [2, 1, 1]}
Response: {"type": "compare_ok", "in_reply_to": 3, "result": "B_BEFORE_A"}

Sample Test Cases

A happens-before BTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"compare","msg_id":2,"clock_a":[2,3,1],"clock_b":[2,4,2]}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "compare_ok", "in_reply_to": 2, "result": "A_BEFORE_B", "msg_id": 1}}

Concurrent events detectedTimeout: 5000ms

Input

{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"compare","msg_id":2,"clock_a":[3,1,0],"clock_b":[1,3,0]}}

Expected Output

{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "compare_ok", "in_reply_to": 2, "result": "CONCURRENT", "msg_id": 1}}

Hints

Hint 1▾

A happens-before B if every element of A <= B and at least one is strictly less

Hint 2▾

Two events are concurrent if neither happens-before the other

Hint 3▾

Implement comparisons as element-wise vector comparison

Hint 4▾

Equal vectors mean the same event (not concurrent)

Hint 5▾

This is a partial order, not a total order

Resources

Detecting Causal Relationships Using Vector Clocks

Wikipedia overview of vector clocks and the happens-before relation

                      OVERVIEW
                    

Theoretical Hub

Concept overview coming soon

Key Concepts

happens-beforeconcurrency detectionpartial ordercausality

main.py

python