TASK
Implementation
Google Spanner's TrueTime API returns a time interval instead of a point: now() -> [earliest, latest]. The true time is guaranteed to be within this interval.
Implement a mock TrueTime with configurable uncertainty:
Request: {"type": "truetime_now", "msg_id": 1}
Response: {"type": "truetime_now_ok", "in_reply_to": 1, "earliest": 1234560, "latest": 1234574, "uncertainty_ms": 7}
Request: {"type": "set_uncertainty", "msg_id": 2, "uncertainty_ms": 10}
Response: {"type": "set_uncertainty_ok", "in_reply_to": 2}Sample Test Cases
TrueTime now returns intervalTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"truetime_now","msg_id":2}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Set uncertaintyTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"set_uncertainty","msg_id":2,"uncertainty_ms":20}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "set_uncertainty_ok", "in_reply_to": 2, "msg_id": 1}}
Hints
Hint 1▾
TrueTime returns [earliest, latest] instead of a single timestamp
Hint 2▾
The uncertainty window is typically ~7ms with GPS/atomic clocks
Hint 3▾
earliest = now - uncertainty, latest = now + uncertainty
Hint 4▾
Any event that happened at real time T has T within [earliest, latest]
Hint 5▾
This is what Google Spanner uses for external consistency
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
TrueTimeGoogle Spanneruncertainty intervalbounded error
main.py
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/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.
uncertainty_ms=7
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)
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=="truetime_now":pass
elif t=="set_uncertainty":pass
if __name__=="__main__":main()