TASK
Implementation
LWW silently loses data when two clients write concurrently. Your task is to demonstrate this and implement a version-vector alternative that detects conflicts.
Implement two modes: lww (last-writer-wins) and vv (version-vector):
Request: {"type": "set_mode", "msg_id": 1, "mode": "vv"}
Response: {"type": "set_mode_ok", "in_reply_to": 1}
Request: {"type": "vv_write", "msg_id": 2, "key": "x", "value": "a", "context": {}}
Response: {"type": "vv_write_ok", "in_reply_to": 2, "vc": {"c1": 1}}
Request: {"type": "vv_read", "msg_id": 3, "key": "x"}
Response: {"type": "vv_read_ok", "in_reply_to": 3, "values": [{"value": "a", "vc": {"c1": 1}}], "conflict": false}When concurrent writes happen in vv mode, both values are preserved:
Response: {"type": "vv_read_ok", "values": [{"value": "a", "vc": {"c1": 1}}, {"value": "b", "vc": {"c2": 1}}], "conflict": true}Sample Test Cases
Set mode to vvTimeout: 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_mode","msg_id":2,"mode":"vv"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "set_mode_ok", "in_reply_to": 2, "msg_id": 1}}
Single vv_write and read, no conflictTimeout: 5000ms
Input
{"src":"c0","dest":"n1","body":{"type":"init","msg_id":1,"node_id":"n1","node_ids":["n1"]}}
{"src":"c1","dest":"n1","body":{"type":"vv_write","msg_id":2,"key":"x","value":"a","context":{}}}
{"src":"c1","dest":"n1","body":{"type":"vv_read","msg_id":3,"key":"x"}}
Expected Output
{"src": "n1", "dest": "c0", "body": {"type": "init_ok", "in_reply_to": 1, "msg_id": 0}}
{"src": "n1", "dest": "c1", "body": {"type": "vv_write_ok", "vc": {"c1": 1}, "in_reply_to": 2, "msg_id": 1}}
{"src": "n1", "dest": "c1", "body": {"type": "vv_read_ok", "values": [{"value": "a", "vc": {"c1": 1}}], "conflict": false, "in_reply_to": 3, "msg_id": 2}}
Hints
Hint 1▾
LWW silently discards the loser in concurrent writes
Hint 2▾
Construct a scenario: client A writes x=1, client B writes x=2 at nearly the same time
Hint 3▾
The write with the lower timestamp is lost forever
Hint 4▾
Version vectors can detect this conflict instead of silently resolving it
Hint 5▾
Return both values as siblings when conflict is detected
OVERVIEW
Theoretical Hub
Concept overview coming soon
Key Concepts
LWW limitationdata lossversion vectorsconflict 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
#!/usr/bin/env python3
import sys
import json
import time
def vc_dominates(a, b):
keys = set(list(a.keys()) + list(b.keys()))
return (all(a.get(k,0) >= b.get(k,0) for k in keys) and
any(a.get(k,0) > b.get(k,0) for k in keys))
class Node:
def __init__(self):
self.node_id = None
self.node_ids = []
self.next_msg_id = 0
self.lww_store = {}
self.vv_store = {}
self.mode = "lww"
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 == "set_mode":