TASK
Implementation
Time-based leases break when clocks drift. Two nodes can both believe they hold a valid lease simultaneously, causing split-brain.
Implement lease management with clock drift simulation:
Request: {"type": "acquire_lease", "msg_id": 1, "duration_ms": 5000}
Response: {"type": "acquire_lease_ok", "in_reply_to": 1, "expires_at": 1234572000}
Request: {"type": "check_lease", "msg_id": 2}
Response: {"type": "check_lease_ok", "in_reply_to": 2, "valid": true, "remaining_ms": 3000}Sample Test Cases
Acquire lease returns expires_atTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"acquire_lease","msg_id":2,"duration_ms":5000}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Check lease shows validTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"acquire_lease","msg_id":2,"duration_ms":60000}}
{"src":"c1","dest":"n1","body":{"type":"check_lease","msg_id":3}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Hints
Hint 1▾
A lease grants leadership for a duration based on local clock
Hint 2▾
If two nodes clocks drift apart, both may think their lease is valid
Hint 3▾
This is the fundamental problem with time-based distributed locks
Hint 4▾
Track lease state and detect overlapping valid leases
Hint 5▾
Simulate by giving each node a different clock offset
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
split-brainleaseclock driftleader election
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/env python3
import sys, json, time
class Node:
def __init__(self):
self.node_id=None;self.node_ids=[];self.next_msg_id=0;self.offset=0;
self.lease_expires=0
def send(self,d,b):b["msg_id"]=self.next_msg_id;self.next_msg_id+=1;print
(json.dumps({"src":self.node_id,"dest":d,"body":b}),flush=True)
def reply(self,r,b):b["in_reply_to"]=r["body"]["msg_id"];self.send(r
["src"],b)
def now_ms(self):return int(time.time()*1000)+self.offset
def main():
node=Node()
for line in sys.stdin:
line=line.strip()
if not line:continue
msg=json.loads(line);body=msg["body"];t=body["type"]
if t=="init":node.node_id=body["node_id"];node.node_ids=body
["node_ids"];node.reply(msg,{"type":"init_ok"})
elif t=="acquire_lease":pass
elif t=="check_lease":pass
elif t=="simulate_drift":node.offset+=body["offset_ms"];node.reply
(msg,{"type":"simulate_drift_ok"})
if __name__=="__main__":main()