FA-75196 / CRDT convergence / Open access

LWW map with delete-wins ties: tombstones are listed as keys with null values · case 01

Deleted keys appear in the document with a null value.

Verified by executionVariant 1 · 9 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The visible projection includes tombstone entries.

THE FAILURE

The visible projection includes tombstone entries.

Unsuccessful approach: Filtering on a null value also hides keys that were explicitly set to null.

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
            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() ) 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', None]], [['k', None]]]`	`[[], []]`	Failed
late local put older than a delete is ignored	`[[['x', None]], []]`	`[[], []]`	Failed
newer put after delete revives the key	`[[['x', 'q']], [['x', 'q']]]`	`[[['x', 'q']], [['x', 'q']]]`	Passed
delete wins a timestamp tie	`[[['y', None]], [['y', None]]]`	`[[], []]`	Failed
delete from a smaller writer still wins the tie	`[[['y', None]], [['y', None]]]`	`[[], []]`	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', None]], [['w', None]]]`	`[[], []]`	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 / 82729a6fc1fbbbfcaa301c9789c7ac7bfb479ed990e362391ee7325a9a81e790

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()):
                offer(d, key, list(entry))
    return [sorted([k, e[0]] for k, e in M[r].items() if e[0] is not None) 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]], [['m', 1]]]`	`[[['m', 1], ['n', None]], [['m', 1], ['n', None]]]`	Failed
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 / 3ee2754429d7e47df2147d0947d17c8dfa221dca581251722590abbbd63a464e

HELD IN THE MEMBER ARCHIVE

The verified repair and its recorded checks are member-only.

This mechanism has 9 recorded checks per implementation. The open-access tier publishes the failure and the unsuccessful fix; the repaired source that passes every check, and the observations that prove it, are available to members.

Every case sharing this mechanism uses the same contract and the same repair, so this one record is held back for all of them.

Member access is invitation-based. Sign in with your invited account to inspect the repair.

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.867454+00:00.

Case digest / 2dba40eb09305d77860cf85ca5edf2ef7aca741fa46940b531cc293543bc5113