TASK
Implementation
A Last-Writer-Wins (LWW) register resolves conflicts by always keeping the value with the latest timestamp. This is simple but can lose concurrent writes.
Implement an LWW key-value store:
Request: {"type": "write", "msg_id": 1, "key": "x", "value": "hello"}
Response: {"type": "write_ok", "in_reply_to": 1, "ts": 1704067200.123}
Request: {"type": "kv_read", "msg_id": 2, "key": "x"}
Response: {"type": "kv_read_ok", "in_reply_to": 2, "key": "x", "value": "hello", "ts": 1704067200.123}
Request: {"type": "kv_merge", "msg_id": 3, "entries": {"x": {"value": "world", "ts": 1704067201.0}}}
Response: {"type": "kv_merge_ok", "in_reply_to": 3, "updated": 1}Sample Test Cases
Write and read backTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"write","msg_id":2,"key":"x","value":"hi"}}
{"src":"c1","dest":"n1","body":{"type":"kv_read","msg_id":3,"key":"x"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
Read missing key returns errorTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"kv_read","msg_id":2,"key":"missing"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "error", "code": 20, "text": "Key not found", "in_reply_to": 2, "msg_id": 1}}
Hints
Hint 1▾
Each value is paired with a timestamp from when it was written
Hint 2▾
On merge, keep the value with the higher timestamp
Hint 3▾
If timestamps tie, use a deterministic tiebreaker (e.g., node ID comparison)
Hint 4▾
LWW is simple but can silently lose concurrent writes
Hint 5▾
Use time.time() for timestamps
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
LWW registerconflict resolutiontimestamp orderinggossip replication
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
#!/usr/bin/env python3
import sys
import json
import time
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.store = {} # key -> {value, ts}
def send(self, dest, body):
body["msg_id"] = self.next_msg_id
self.next_msg_id += 1
print(json.dumps({"src": self.node_id, "dest": dest, "body": body}),
flush=True)
def reply(self, req, body):
body["in_reply_to"] = req["body"]["msg_id"]
self.send(req["src"], body)
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 == "write":
ts = time.time()
node.store[body["key"]] = {"value": body["value"], "ts": ts}
node.reply(msg, {"type": "write_ok", "ts": ts})
elif t == "kv_read":
k = body["key"]
if k in node.store:
e = node.store[k]