TASK
Implementation
The HLC receive rule is more complex than Lamport's. On receiving a message with HLC (msg.pt, msg.lc):
new_pt = max(local.pt, msg.pt, now_ms())- If
new_pt == local.pt == msg.pt:new_lc = max(local.lc, msg.lc) + 1 - Elif
new_pt == local.pt:new_lc = local.lc + 1 - Elif
new_pt == msg.pt:new_lc = msg.lc + 1 - Else (new physical time):
new_lc = 0
Implement a hlc_receive handler:
Request: {"type": "hlc_receive", "msg_id": 1, "remote_pt": 1000, "remote_lc": 5}
Response: {"type": "hlc_receive_ok", "in_reply_to": 1, "pt": 1000, "lc": 6}Sample Test Cases
Receive from ahead remote advances localTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"n2","dest":"n1","body":{"type":"hlc_receive","msg_id":2,"remote_pt":9999999999999,"remote_lc":5}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "n2", "body": {"type": "hlc_receive_ok", "pt": 9999999999999, "lc": 6, "in_reply_to": 2, "msg_id": 1}}
Receive from behind remote uses localTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"hlc_tick","msg_id":2}}
{"src":"n2","dest":"n1","body":{"type":"hlc_receive","msg_id":3,"remote_pt":0,"remote_lc":0}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
On receive: take max of local pt, received pt, and current physical time
Hint 2▾
If the max pt equals local pt and received pt, increment lc from max of both lc values
Hint 3▾
If max pt equals only one side, take that sides lc and increment
Hint 4▾
If max pt is the new physical time, reset lc to 0
Hint 5▾
HLC must always advance - never go backward
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
HLC mergereceive ruleclock synchronizationcausal consistency
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
import time
class HLC:
def __init__(self):
self.pt = 0
self.lc = 0
def now_ms(self):
return int(time.time() * 1000)
def tick(self):
now = self.now_ms()
if now > self.pt:
self.pt = now
self.lc = 0
else:
self.lc += 1
return self.get()
def receive(self, remote_pt, remote_lc):
# TODO: Implement the HLC receive rule
pass
def get(self):
return {"pt": self.pt, "lc": self.lc}
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.hlc = HLC()
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}