TASK
Implementation
With vector clocks, you can determine the exact causal relationship between any two events:
- A -> B (A happened before B): A[i] <= B[i] for all i, and strict < for at least one
- B -> A (B happened before A): B[i] <= A[i] for all i, and strict < for at least one
- A || B (concurrent): neither dominates
Implement a compare handler:
Request: {"type": "compare", "msg_id": 1,
"vc_a": {"n1": 2, "n2": 1},
"vc_b": {"n1": 1, "n2": 3}}
Response: {"type": "compare_ok", "in_reply_to": 1, "relation": "concurrent"}Possible relations: "a_before_b", "b_before_a", "concurrent", "equal".
Sample Test Cases
A 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,"vc_a":{"n1":1,"n2":0},"vc_b":{"n1":2,"n2":1}}}
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", "relation": "a_before_b", "in_reply_to": 2, "msg_id": 1}}
Concurrent eventsTimeout: 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,"vc_a":{"n1":2,"n2":1},"vc_b":{"n1":1,"n2":3}}}
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", "relation": "concurrent", "in_reply_to": 2, "msg_id": 1}}
Hints
Hint 1▾
A -> B if A[i] <= B[i] for all i, and A[j] < B[j] for at least one j
Hint 2▾
A || B (concurrent) if neither A -> B nor B -> A
Hint 3▾
Compare vectors element-wise across all nodes
Hint 4▾
Store events with their vector clock snapshots for later comparison
Hint 5▾
This is the foundation for conflict detection in databases like Riak
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
happened-beforeconcurrent eventsvector comparisonconflict detection
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#!/usr/bin/env python3
import sys
import json
def compare_vectors(vc_a, vc_b):
# TODO: Compare two vector clocks
# Return "a_before_b", "b_before_a", "concurrent", or "equal"
pass
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
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:
line = line.strip()
if not line:
continue
message = json.loads(line)
body = message["body"]
msg_type = body["type"]
if msg_type == "init":
node.node_id = body["node_id"]
node.node_ids = body["node_ids"]
node.reply(message, {"type": "init_ok"})
elif msg_type == "compare":
# TODO: Compare two vector clocks