FA-75186 / CRDT convergence / Open access
LWW map with delete-wins ties: deletes drop the key instead of storing a tombstone · case 01
A stale put arriving by merge brings a deleted key back.
ROOT CAUSE
The delete removes the entry, leaving nothing with a timestamp to beat older puts.
VERIFIED REPAIR
Store deletes as timestamped tombstones and compare them like any other entry.
Unsuccessful approach: Keeping tombstones locally but not shipping them in merges still lets peers resurrect the key.
Case contract
Each key holds [value, ts, kind, writer] with kind 1 for a delete tombstone and 0 for a put. An incoming entry (local op or merge) replaces the stored one only if (ts, kind, writer) is lexicographically larger, so deletes win timestamp ties and writers break the rest. Tombstones are kept. ["merge", s, d] offers each of s's entries to d. Return sorted visible [key, value] pairs per replica.
Why this case matters
Document CRDTs built from per-field LWW registers must not let stale writes resurrect deleted fields.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
M = {r: {} for r in replicas}
def offer(r, key, entry):
cur = M[r].get(key)
if cur is None or (entry[1], entry[2], entry[3]) > (cur[1], cur[2], cur[3]):
M[r][key] = entry
for op in ops:
if op[0] == 'put':
_, r, key, value, ts = op
offer(r, key, [value, ts, 0, r])
elif op[0] == 'del':
_, r, key, ts = op
M[r].pop(key, None)
else:
s, d = op[1], op[2]
for key, entry in list(M[s].items()):
offer(d, key, list(entry))
return [sorted([k, e[0]] for k, e in M[r].items() if e[2] == 0) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 2], ['put', 'b', 'k', 'old', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 4], ['put', 'a', 'x', 2, 2]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 1], ['del', 'b', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 1], ['del', 'a', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 1], ['put', 'b', 'z', 'zb', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 1, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 1], ['n', None]], [['m', 1], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 2], ['put', 'a', 'w', 'late', 1], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]])],
2: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 3], ['put', 'b', 'k', 'old', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 5], ['put', 'a', 'x', 2, 3]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 2], ['del', 'b', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 2], ['del', 'a', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 2], ['put', 'b', 'z', 'zb', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 2, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 2], ['n', None]], [['m', 2], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 3], ['put', 'a', 'w', 'late', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2]], [['k0', 0], ['k1', 1], ['k2', 2], ['q', 'bq']]])],
3: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 4], ['put', 'b', 'k', 'old', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 6], ['put', 'a', 'x', 2, 4]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 3], ['del', 'b', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 3], ['del', 'a', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 3], ['put', 'b', 'z', 'zb', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 3, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 3], ['n', None]], [['m', 3], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 4], ['put', 'a', 'w', 'late', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['q', 'bq']]])],
4: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 5], ['put', 'b', 'k', 'old', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 7], ['put', 'a', 'x', 2, 5]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 4], ['del', 'b', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 4], ['del', 'a', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 4], ['put', 'b', 'z', 'zb', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 4, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 4], ['n', None]], [['m', 4], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 5], ['put', 'a', 'w', 'late', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['q', 'bq']]])],
5: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 6], ['put', 'b', 'k', 'old', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 8], ['put', 'a', 'x', 2, 6]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 7], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 5], ['del', 'b', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 5], ['del', 'a', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 5], ['put', 'b', 'z', 'zb', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 5, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 5], ['n', None]], [['m', 5], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 6], ['put', 'a', 'w', 'late', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'a', 'k5', 5, 6], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5], ['q', 'bq']]])],
}[N]
for label, args, expected in cases:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| delete then stale put via merge stays deleted | [[['k', 'old']], [['k', 'old']]] | [[], []] | Failed |
| late local put older than a delete is ignored | [[['x', 2]], []] | [[], []] | Failed |
| newer put after delete revives the key | [[['x', 'q']], [['x', 'q']]] | [[['x', 'q']], [['x', 'q']]] | Passed |
| delete wins a timestamp tie | [[['y', 'ya']], [['y', 'ya']]] | [[], []] | Failed |
| delete from a smaller writer still wins the tie | [[['y', 'yb']], [['y', 'yb']]] | [[], []] | Failed |
| writer breaks ties between puts | [[['z', 'zb']], [['z', 'zb']]] | [[['z', 'zb']], [['z', 'zb']]] | Passed |
| null values are real values | [[['m', 1], ['n', None]], [['m', 1], ['n', None]]] | [[['m', 1], ['n', None]], [['m', 1], ['n', None]]] | Passed |
| tombstone propagates without a prior put | [[['w', 'late']], []] | [[], []] | Failed |
| independent keys merge | [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]] | [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]] | Passed |
SHA-256 / 8cd7994dc2cf06db09980178984c2dc5bd19ee6fa33b3506c72f3ed11cfeaf40
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
M = {r: {} for r in replicas}
def offer(r, key, entry):
cur = M[r].get(key)
if cur is None or (entry[1], entry[2], entry[3]) > (cur[1], cur[2], cur[3]):
M[r][key] = entry
for op in ops:
if op[0] == 'put':
_, r, key, value, ts = op
offer(r, key, [value, ts, 0, r])
elif op[0] == 'del':
_, r, key, ts = op
offer(r, key, [None, ts, 1, r])
else:
s, d = op[1], op[2]
for key, entry in list(M[s].items()):
if entry[2] == 0:
offer(d, key, list(entry))
return [sorted([k, e[0]] for k, e in M[r].items() if e[2] == 0) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 2], ['put', 'b', 'k', 'old', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 4], ['put', 'a', 'x', 2, 2]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 1], ['del', 'b', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 1], ['del', 'a', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 1], ['put', 'b', 'z', 'zb', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 1, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 1], ['n', None]], [['m', 1], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 2], ['put', 'a', 'w', 'late', 1], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]])],
2: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 3], ['put', 'b', 'k', 'old', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 5], ['put', 'a', 'x', 2, 3]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 2], ['del', 'b', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 2], ['del', 'a', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 2], ['put', 'b', 'z', 'zb', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 2, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 2], ['n', None]], [['m', 2], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 3], ['put', 'a', 'w', 'late', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2]], [['k0', 0], ['k1', 1], ['k2', 2], ['q', 'bq']]])],
3: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 4], ['put', 'b', 'k', 'old', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 6], ['put', 'a', 'x', 2, 4]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 3], ['del', 'b', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 3], ['del', 'a', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 3], ['put', 'b', 'z', 'zb', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 3, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 3], ['n', None]], [['m', 3], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 4], ['put', 'a', 'w', 'late', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['q', 'bq']]])],
4: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 5], ['put', 'b', 'k', 'old', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 7], ['put', 'a', 'x', 2, 5]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 4], ['del', 'b', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 4], ['del', 'a', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 4], ['put', 'b', 'z', 'zb', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 4, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 4], ['n', None]], [['m', 4], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 5], ['put', 'a', 'w', 'late', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['q', 'bq']]])],
5: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 6], ['put', 'b', 'k', 'old', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 8], ['put', 'a', 'x', 2, 6]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 7], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 5], ['del', 'b', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 5], ['del', 'a', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 5], ['put', 'b', 'z', 'zb', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 5, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 5], ['n', None]], [['m', 5], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 6], ['put', 'a', 'w', 'late', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'a', 'k5', 5, 6], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5], ['q', 'bq']]])],
}[N]
for label, args, expected in cases:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| delete then stale put via merge stays deleted | [[], [['k', 'old']]] | [[], []] | Failed |
| late local put older than a delete is ignored | [[], []] | [[], []] | Passed |
| newer put after delete revives the key | [[['x', 'q']], [['x', 'q']]] | [[['x', 'q']], [['x', 'q']]] | Passed |
| delete wins a timestamp tie | [[['y', 'ya']], []] | [[], []] | Failed |
| delete from a smaller writer still wins the tie | [[], [['y', 'yb']]] | [[], []] | Failed |
| writer breaks ties between puts | [[['z', 'zb']], [['z', 'zb']]] | [[['z', 'zb']], [['z', 'zb']]] | Passed |
| null values are real values | [[['m', 1], ['n', None]], [['m', 1], ['n', None]]] | [[['m', 1], ['n', None]], [['m', 1], ['n', None]]] | Passed |
| tombstone propagates without a prior put | [[['w', 'late']], []] | [[], []] | Failed |
| independent keys merge | [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]] | [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]] | Passed |
SHA-256 / 0c9d31fe10924f7faef56e7b1200c92a856484595db73343ad465d66dab6c50f
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
M = {r: {} for r in replicas}
def offer(r, key, entry):
cur = M[r].get(key)
if cur is None or (entry[1], entry[2], entry[3]) > (cur[1], cur[2], cur[3]):
M[r][key] = entry
for op in ops:
if op[0] == 'put':
_, r, key, value, ts = op
offer(r, key, [value, ts, 0, r])
elif op[0] == 'del':
_, r, key, ts = op
offer(r, key, [None, ts, 1, r])
else:
s, d = op[1], op[2]
for key, entry in list(M[s].items()):
offer(d, key, list(entry))
return [sorted([k, e[0]] for k, e in M[r].items() if e[2] == 0) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 2], ['put', 'b', 'k', 'old', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 4], ['put', 'a', 'x', 2, 2]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 1], ['del', 'b', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 1], ['del', 'a', 'y', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 1], ['put', 'b', 'z', 'zb', 1], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 1, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 1], ['n', None]], [['m', 1], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 2], ['put', 'a', 'w', 'late', 1], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]])],
2: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 3], ['put', 'b', 'k', 'old', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 5], ['put', 'a', 'x', 2, 3]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 2], ['del', 'b', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 2], ['del', 'a', 'y', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 2], ['put', 'b', 'z', 'zb', 2], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 2, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 2], ['n', None]], [['m', 2], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 3], ['put', 'a', 'w', 'late', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2]], [['k0', 0], ['k1', 1], ['k2', 2], ['q', 'bq']]])],
3: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 4], ['put', 'b', 'k', 'old', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 6], ['put', 'a', 'x', 2, 4]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 3], ['del', 'b', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 3], ['del', 'a', 'y', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 3], ['put', 'b', 'z', 'zb', 3], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 3, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 3], ['n', None]], [['m', 3], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 4], ['put', 'a', 'w', 'late', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['q', 'bq']]])],
4: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 5], ['put', 'b', 'k', 'old', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 7], ['put', 'a', 'x', 2, 5]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 4], ['del', 'b', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 4], ['del', 'a', 'y', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 4], ['put', 'b', 'z', 'zb', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 4, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 4], ['n', None]], [['m', 4], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 5], ['put', 'a', 'w', 'late', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['q', 'bq']]])],
5: [('delete then stale put via merge stays deleted', [[['put', 'a', 'k', 'v1', 1], ['merge', 'a', 'b'], ['del', 'a', 'k', 6], ['put', 'b', 'k', 'old', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('late local put older than a delete is ignored', [[['put', 'a', 'x', 1, 1], ['del', 'a', 'x', 8], ['put', 'a', 'x', 2, 6]], ['a', 'b']], [[], []]), ('newer put after delete revives the key', [[['put', 'a', 'x', 'p', 1], ['del', 'b', 'x', 2], ['put', 'a', 'x', 'q', 7], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [[['x', 'q']], [['x', 'q']]]), ('delete wins a timestamp tie', [[['put', 'a', 'y', 'ya', 5], ['del', 'b', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('delete from a smaller writer still wins the tie', [[['put', 'b', 'y', 'yb', 5], ['del', 'a', 'y', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('writer breaks ties between puts', [[['put', 'a', 'z', 'za', 5], ['put', 'b', 'z', 'zb', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [[['z', 'zb']], [['z', 'zb']]]), ('null values are real values', [[['put', 'a', 'n', None, 1], ['put', 'a', 'm', 5, 2], ['merge', 'a', 'b']], ['a', 'b']], [[['m', 5], ['n', None]], [['m', 5], ['n', None]]]), ('tombstone propagates without a prior put', [[['del', 'b', 'w', 6], ['put', 'a', 'w', 'late', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('independent keys merge', [[['put', 'a', 'k0', 0, 1], ['put', 'a', 'k1', 1, 2], ['put', 'a', 'k2', 2, 3], ['put', 'a', 'k3', 3, 4], ['put', 'a', 'k4', 4, 5], ['put', 'a', 'k5', 5, 6], ['put', 'b', 'q', 'bq', 1], ['merge', 'a', 'b']], ['a', 'b']], [[['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5]], [['k0', 0], ['k1', 1], ['k2', 2], ['k3', 3], ['k4', 4], ['k5', 5], ['q', 'bq']]])],
}[N]
for label, args, expected in cases:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| delete then stale put via merge stays deleted | [[], []] | [[], []] | Passed |
| late local put older than a delete is ignored | [[], []] | [[], []] | Passed |
| newer put after delete revives the key | [[['x', 'q']], [['x', 'q']]] | [[['x', 'q']], [['x', 'q']]] | Passed |
| delete wins a timestamp tie | [[], []] | [[], []] | Passed |
| delete from a smaller writer still wins the tie | [[], []] | [[], []] | Passed |
| writer breaks ties between puts | [[['z', 'zb']], [['z', 'zb']]] | [[['z', 'zb']], [['z', 'zb']]] | Passed |
| null values are real values | [[['m', 1], ['n', None]], [['m', 1], ['n', None]]] | [[['m', 1], ['n', None]], [['m', 1], ['n', None]]] | Passed |
| tombstone propagates without a prior put | [[], []] | [[], []] | Passed |
| independent keys merge | [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]] | [[['k0', 0], ['k1', 1]], [['k0', 0], ['k1', 1], ['q', 'bq']]] | Passed |
SHA-256 / 4cbb608cd4b4b230533ad562151c1e63527e0db9ce59373ebfa985b6a27822c8
Verification & scope
A deterministic, bounded teaching model of one replicated data type with stipulated operation and merge rules; it is not a production CRDT library and makes no claim of conformance to any specific published design. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:49:03.770006+00:00.
Case digest / f497a8cee65ef7556750cee79ea7aa8c3169c36cbbe04c57b5f16a83c048136b