crdt-lwwmap-convergent-merge
Model. The LWW-Element-Map (Shapiro et al. 2011) stores, per key, the winning add event and the winning remove event. Every event carries (timestamp, replica_id), and events are totally ordered by lexicographic (timestamp, replica_id) — so concurrent writes with colliding timestamps (clock skew, equal logical clocks) tie-break deterministically on replica_id. Deletions are tombstones that are never dropped; they are only ever displaced by a strictly larger remove. A key is present iff its winning add is strictly greater than its winning remove.
Merge. merge(a,b) is the per-key max of the two states' add entries and remove entries. Since max over a total order with a bottom element ("no event") is a join-semilattice, merge is automatically commutative, associative, and idempotent. The value rides along with the add entry (ts, rid, value), so the winner's value — not the local one — survives the merge.
Code (~/crdt_lwwmap.py):
class LWWElementMap:
def __init__(self, replica_id: str):
self.replica_id = replica_id
self._adds: Dict[Any, Tuple[int, str, Any]] = {} # key -> (ts, rid, value)
self._removes: Dict[Any, Tuple[int, str]] = {} # key -> (ts, rid) tombstone
self._clock = itertools.count(1)
def put(self, key, value, timestamp=None):
ts = next(self._clock) if timestamp is None else timestamp
entry = (ts, self.replica_id, value)
cur = self._adds.get(key)
if cur is None or (ts, self.replica_id) > (cur[0], cur[1]):
self._adds[key] = entry
def remove(self, key, timestamp=None):
ts = next(self._clock) if timestamp is None else timestamp
entry = (ts, self.replica_id)
cur = self._removes.get(key)
if cur is None or entry > cur:
self._removes[key] = entry # tombstone: kept forever
def lookup(self, key):
add = self._adds.get(key)
if add is None: return None
rem = self._removes.get(key)
if rem is not None and rem >= (add[0], add[1]): return None # tombstone wins
return add[2]
def merge(self, other): # pure; returns new map
out = LWWElementMap(self.replica_id)
out._adds = dict(self._adds)
for key, (ts, rid, value) in other._adds.items():
cur = out._adds.get(key)
if cur is None or (ts, rid) > (cur[0], cur[1]):
out._adds[key] = (ts, rid, value)
out._removes = dict(self._removes)
for key, entry in other._removes.items():
cur = out._removes.get(key)
if cur is None or entry > cur:
out._removes[key] = entry
return out
Convergence proof (3-way concurrent merge). Write the state as x = (A_x, R_x), with A_x(k) = max add event for k and R_x(k) = max remove event for k, where a missing event is the bottom element ⊥. Define (f ∨ g)(k) = max(f(k), g(k)) under ≺ (lexicographic (ts, rid)). Then merge(x,y) = (A_x ∨ A_y, R_x ∨ R_y), and:
f ∨ g = g ∨ f (max is symmetric).(f ∨ g) ∨ h = f ∨ (g ∨ h) (max is associative).f ∨ f = f.Therefore merge(merge(a,b), c)(k) = max(max(a(k),b(k)), c(k)) = max(c(k), max(a(k),b(k))) = merge(c, merge(a,b))(k) for both components and every key — so the two 3-way orders produce identical states, identical tombstones, and identical lookups. By induction this holds for any pairwise-merge schedule over n replicas: all schedules converge to the pointwise max of all replica states in one step.
The subtle case: deleted key concurrently re-added. B does put(k,v,10) then remove(k,20); C (which never saw B's remove) does put(k,w,15) — a concurrent re-add with a stale clock. Merged: A(k) = (15,C), R(k) = (20,B), and since (20,B) ≻ (15,C), k stays deleted. The tombstone (20,B) is retained, so a third replica that only knows the original add (put(k,v',10)) cannot resurrect k either — max over adds is still (15,C) or (10,·), both beaten by (20,B). If instead C re-adds with ts = 30 > 20, the add legitimately wins and k is present with w — deterministic in both merge orders. Crucially, tombstones are never garbage-collected, because even a tombstone currently dominated by a newer add still bounds future concurrent removes; dropping it would break the semilattice and allow divergence.
Verification: `python3 test_crdt_lwwmap.py` and `python3 -m pytest -q` — **16/16 tests pass** in both runners (Python 3.11+ semantics; ran on 3.14). ``` PASS test_basic_put_lookup PASS test_remove_wins_over_older_add PASS test_remove_of_absent_key_records_tombstone PASS test_commutative PASS test_associative PASS test_idempotent PASS test_three_way_merge_problem_scenario PASS test_concurrent_readd_stale_timestamp_stays_deleted PASS test_concurrent_readd_fresh_timestamp_wins PASS test_tombstones_block_resurrection_across_third_replica PASS test_tie_break_same_timestamp_deterministic PASS test_value_rides_with_winning_add PASS test_tombstones_retained_in_merge_result PASS test_inplace_merge_equals_pure_merge PASS test_randomized_all_merge_orders_converge PASS test_randomized_three_way_law 16 passed, 0 failed, 16 total ``` Edge cases covered: - **Exact problem law:** `merge(merge(a,b),c) == merge(c, merge(a,b))` with equal states *including tombstones* (snapshot equality, not just lookups). - **Deleted + concurrent stale re-add** (`add 15 < remove 20`): key stays deleted in both merge orders; tombstone `(20,b)` retained. - **Fresh re-add** (`add 30 > remove 20`): re-add wins with the correct value. - **Resurrection blocked across a third replica** that only ever saw the original add. - **Timestamp tie-break:** `(5,"a")` vs `(5,"b")` resolves deterministically to `(5,"b")`; remove `(5,"c")` beats add `(5,"b")` — identical results in both orders. - **Value integrity:** merge keeps the value belonging to the winning `(ts, rid)`. - **Tombstones retained even when dominated** by a newer add (GC safety argument). - **Randomized stress:** 20 seeds × 4 replicas × 60 ops with forced timestamp collisions; all 24 permutation-fold orders produce one identical snapshot; plus 20 randomized 3-way law checks with per-key lookup agreement.
{"model": "deepseek-v4-flash", "problem_class": "crdt-lwwmap-convergent-merge", "result": "passed", "tests": 16}Model. The LWW-Element-Map (Shapiro et al. 2011) stores, per key, the winning add event and the winning remove event. Every event carries (timestamp, replica_id), and events are totally ordered by lexicographic (timestamp, replica_id) — so concurrent writes with colliding timestamps (clock skew, equal logical clocks) tie-break deterministically on replica_id. Deletions are tombstones that are never dropped; they are only ever displaced by a strictly larger remove. A key is present iff its winning add is strictly greater than its winning remove.
Merge. merge(a,b) is the per-key max of the two states' add entries and remove entries. Since max over a total order with a bottom element ("no event") is a join-semilattice, merge is automatically commutative, associative, and idempotent. The value rides along with the add entry (ts, rid, value), so the winner's value — not the local one — survives the merge.
Code (~/crdt_lwwmap.py):
class LWWElementMap:
def __init__(self, replica_id: str):
self.replica_id = replica_id
self._adds: Dict[Any, Tuple[int, str, Any]] = {} # key -> (ts, rid, value)
self._removes: Dict[Any, Tuple[int, str]] = {} # key -> (ts, rid) tombstone
self._clock = itertools.count(1)
def put(self, key, value, timestamp=None):
ts = next(self._clock) if timestamp is None else timestamp
entry = (ts, self.replica_id, value)
cur = self._adds.get(key)
if cur is None or (ts, self.replica_id) > (cur[0], cur[1]):
self._adds[key] = entry
def remove(self, key, timestamp=None):
ts = next(self._clock) if timestamp is None else timestamp
entry = (ts, self.replica_id)
cur = self._removes.get(key)
if cur is None or entry > cur:
self._removes[key] = entry # tombstone: kept forever
def lookup(self, key):
add = self._adds.get(key)
if add is None: return None
rem = self._removes.get(key)
if rem is not None and rem >= (add[0], add[1]): return None # tombstone wins
return add[2]
def merge(self, other): # pure; returns new map
out = LWWElementMap(self.replica_id)
out._adds = dict(self._adds)
for key, (ts, rid, value) in other._adds.items():
cur = out._adds.get(key)
if cur is None or (ts, rid) > (cur[0], cur[1]):
out._adds[key] = (ts, rid, value)
out._removes = dict(self._removes)
for key, entry in other._removes.items():
cur = out._removes.get(key)
if cur is None or entry > cur:
out._removes[key] = entry
return out
Convergence proof (3-way concurrent merge). Write the state as x = (A_x, R_x), with A_x(k) = max add event for k and R_x(k) = max remove event for k, where a missing event is the bottom element ⊥. Define (f ∨ g)(k) = max(f(k), g(k)) under ≺ (lexicographic (ts, rid)). Then merge(x,y) = (A_x ∨ A_y, R_x ∨ R_y), and:
f ∨ g = g ∨ f (max is symmetric).(f ∨ g) ∨ h = f ∨ (g ∨ h) (max is associative).f ∨ f = f.Therefore merge(merge(a,b), c)(k) = max(max(a(k),b(k)), c(k)) = max(c(k), max(a(k),b(k))) = merge(c, merge(a,b))(k) for both components and every key — so the two 3-way orders produce identical states, identical tombstones, and identical lookups. By induction this holds for any pairwise-merge schedule over n replicas: all schedules converge to the pointwise max of all replica states in one step.
The subtle case: deleted key concurrently re-added. B does put(k,v,10) then remove(k,20); C (which never saw B's remove) does put(k,w,15) — a concurrent re-add with a stale clock. Merged: A(k) = (15,C), R(k) = (20,B), and since (20,B) ≻ (15,C), k stays deleted. The tombstone (20,B) is retained, so a third replica that only knows the original add (put(k,v',10)) cannot resurrect k either — max over adds is still (15,C) or (10,·), both beaten by (20,B). If instead C re-adds with ts = 30 > 20, the add legitimately wins and k is present with w — deterministic in both merge orders. Crucially, tombstones are never garbage-collected, because even a tombstone currently dominated by a newer add still bounds future concurrent removes; dropping it would break the semilattice and allow divergence.
Verification: `python3 test_crdt_lwwmap.py` and `python3 -m pytest -q` — **16/16 tests pass** in both runners (Python 3.11+ semantics; ran on 3.14). ``` PASS test_basic_put_lookup PASS test_remove_wins_over_older_add PASS test_remove_of_absent_key_records_tombstone PASS test_commutative PASS test_associative PASS test_idempotent PASS test_three_way_merge_problem_scenario PASS test_concurrent_readd_stale_timestamp_stays_deleted PASS test_concurrent_readd_fresh_timestamp_wins PASS test_tombstones_block_resurrection_across_third_replica PASS test_tie_break_same_timestamp_deterministic PASS test_value_rides_with_winning_add PASS test_tombstones_retained_in_merge_result PASS test_inplace_merge_equals_pure_merge PASS test_randomized_all_merge_orders_converge PASS test_randomized_three_way_law 16 passed, 0 failed, 16 total ``` Edge cases covered: - **Exact problem law:** `merge(merge(a,b),c) == merge(c, merge(a,b))` with equal states *including tombstones* (snapshot equality, not just lookups). - **Deleted + concurrent stale re-add** (`add 15 < remove 20`): key stays deleted in both merge orders; tombstone `(20,b)` retained. - **Fresh re-add** (`add 30 > remove 20`): re-add wins with the correct value. - **Resurrection blocked across a third replica** that only ever saw the original add. - **Timestamp tie-break:** `(5,"a")` vs `(5,"b")` resolves deterministically to `(5,"b")`; remove `(5,"c")` beats add `(5,"b")` — identical results in both orders. - **Value integrity:** merge keeps the value belonging to the winning `(ts, rid)`. - **Tombstones retained even when dominated** by a newer add (GC safety argument). - **Randomized stress:** 20 seeds × 4 replicas × 60 ops with forced timestamp collisions; all 24 permutation-fold orders produce one identical snapshot; plus 20 randomized 3-way law checks with per-key lookup agreement.
{"model": "deepseek-v4-flash", "problem_class": "crdt-lwwmap-convergent-merge", "result": "passed", "tests": 16}