{"abstract":"Deleted keys appear in the document with a null value.","category":"CRDT convergence","checks":9,"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.","contract_signature":"ops, replicas","evaluation_group":"w2-crdt-convergence-lww-map-delete-wins","failed_approach":"Filtering on a null value also hides keys that were explicitly set to null.","family":"w2-crdt-convergence-lww-map-delete-wins-visibility-filter","id":"FA-75196","implementations":{"attempt":{"sha256":"3ee2754429d7e47df2147d0947d17c8dfa221dca581251722590abbbd63a464e","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(ops, replicas):\n    M = {r: {} for r in replicas}\n    def offer(r, key, entry):\n        cur = M[r].get(key)\n        if cur is None or (entry[1], entry[2], entry[3]) > (cur[1], cur[2], cur[3]):\n            M[r][key] = entry\n    for op in ops:\n        if op[0] == 'put':\n            _, r, key, value, ts = op\n            offer(r, key, [value, ts, 0, r])\n        elif op[0] == 'del':\n            _, r, key, ts = op\n            offer(r, key, [None, ts, 1, r])\n        else:\n            s, d = op[1], op[2]\n            for key, entry in list(M[s].items()):\n                offer(d, key, list(entry))\n    return [sorted([k, e[0]] for k, e in M[r].items() if e[0] is not None) for r in replicas]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    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']]])],\n    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']]])],\n    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']]])],\n    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']]])],\n    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}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"},"broken":{"sha256":"82729a6fc1fbbbfcaa301c9789c7ac7bfb479ed990e362391ee7325a9a81e790","source":"\"\"\"Failure Map reference implementation. Python standard library only.\"\"\"\nimport json\n\nN = 1\nobservations = []\ndef solve(ops, replicas):\n    M = {r: {} for r in replicas}\n    def offer(r, key, entry):\n        cur = M[r].get(key)\n        if cur is None or (entry[1], entry[2], entry[3]) > (cur[1], cur[2], cur[3]):\n            M[r][key] = entry\n    for op in ops:\n        if op[0] == 'put':\n            _, r, key, value, ts = op\n            offer(r, key, [value, ts, 0, r])\n        elif op[0] == 'del':\n            _, r, key, ts = op\n            offer(r, key, [None, ts, 1, r])\n        else:\n            s, d = op[1], op[2]\n            for key, entry in list(M[s].items()):\n                offer(d, key, list(entry))\n    return [sorted([k, e[0]] for k, e in M[r].items() ) for r in replicas]\ndef check(label, actual, expected):\n    observations.append({\"check\": label, \"actual\": actual, \"expected\": expected, \"passed\": actual == expected})\ncases = {\n    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']]])],\n    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']]])],\n    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']]])],\n    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']]])],\n    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}[N]\nfor label, args, expected in cases:\n    check(label, solve(*args), expected)\nprint(json.dumps({\"observations\": observations, \"passed\": all(x[\"passed\"] for x in observations)}, ensure_ascii=False))\nraise SystemExit(0 if all(x[\"passed\"] for x in observations) else 1)\n"}},"limitations":"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.","method":"Deterministic executable model with adversarial boundary fixtures.","provenance":{"created_by":"Failure Map","dependencies":"Python standard library","family":"w2-crdt-convergence-lww-map-delete-wins-visibility-filter","generated_at":"2026-09-29T14:49:03.867454+00:00","license":"CC0-1.0","python":"3.12.14","seed":1,"split":"open-access"},"relevance":"Document CRDTs built from per-field LWW registers must not let stale writes resurrect deleted fields.","root_cause":"The visible projection includes tombstone entries.","sha256":"2dba40eb09305d77860cf85ca5edf2ef7aca741fa46940b531cc293543bc5113","title":"LWW map with delete-wins ties: tombstones are listed as keys with null values · case 01","variant":1,"variant_policy":"Five numbered records share a model and may reuse boundary fixtures.","verified":true,"visibility":"public","verification":{"attempt":{"elapsed_ms":42.812,"exit_code":1,"observations":[{"actual":[[],[]],"check":"delete then stale put via merge stays deleted","expected":[[],[]],"passed":true},{"actual":[[],[]],"check":"late local put older than a delete is ignored","expected":[[],[]],"passed":true},{"actual":[[["x","q"]],[["x","q"]]],"check":"newer put after delete revives the key","expected":[[["x","q"]],[["x","q"]]],"passed":true},{"actual":[[],[]],"check":"delete wins a timestamp tie","expected":[[],[]],"passed":true},{"actual":[[],[]],"check":"delete from a smaller writer still wins the tie","expected":[[],[]],"passed":true},{"actual":[[["z","zb"]],[["z","zb"]]],"check":"writer breaks ties between puts","expected":[[["z","zb"]],[["z","zb"]]],"passed":true},{"actual":[[["m",1]],[["m",1]]],"check":"null values are real values","expected":[[["m",1],["n",null]],[["m",1],["n",null]]],"passed":false},{"actual":[[],[]],"check":"tombstone propagates without a prior put","expected":[[],[]],"passed":true},{"actual":[[["k0",0],["k1",1]],[["k0",0],["k1",1],["q","bq"]]],"check":"independent keys merge","expected":[[["k0",0],["k1",1]],[["k0",0],["k1",1],["q","bq"]]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"delete then stale put via merge stays deleted\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}, {\"check\": \"late local put older than a delete is ignored\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}, {\"check\": \"newer put after delete revives the key\", \"actual\": [[[\"x\", \"q\"]], [[\"x\", \"q\"]]], \"expected\": [[[\"x\", \"q\"]], [[\"x\", \"q\"]]], \"passed\": true}, {\"check\": \"delete wins a timestamp tie\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}, {\"check\": \"delete from a smaller writer still wins the tie\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}, {\"check\": \"writer breaks ties between puts\", \"actual\": [[[\"z\", \"zb\"]], [[\"z\", \"zb\"]]], \"expected\": [[[\"z\", \"zb\"]], [[\"z\", \"zb\"]]], \"passed\": true}, {\"check\": \"null values are real values\", \"actual\": [[[\"m\", 1]], [[\"m\", 1]]], \"expected\": [[[\"m\", 1], [\"n\", null]], [[\"m\", 1], [\"n\", null]]], \"passed\": false}, {\"check\": \"tombstone propagates without a prior put\", \"actual\": [[], []], \"expected\": [[], []], \"passed\": true}, {\"check\": \"independent keys merge\", \"actual\": [[[\"k0\", 0], [\"k1\", 1]], [[\"k0\", 0], [\"k1\", 1], [\"q\", \"bq\"]]], \"expected\": [[[\"k0\", 0], [\"k1\", 1]], [[\"k0\", 0], [\"k1\", 1], [\"q\", \"bq\"]]], \"passed\": true}], \"passed\": false}\n"},"broken":{"elapsed_ms":40.641,"exit_code":1,"observations":[{"actual":[[["k",null]],[["k",null]]],"check":"delete then stale put via merge stays deleted","expected":[[],[]],"passed":false},{"actual":[[["x",null]],[]],"check":"late local put older than a delete is ignored","expected":[[],[]],"passed":false},{"actual":[[["x","q"]],[["x","q"]]],"check":"newer put after delete revives the key","expected":[[["x","q"]],[["x","q"]]],"passed":true},{"actual":[[["y",null]],[["y",null]]],"check":"delete wins a timestamp tie","expected":[[],[]],"passed":false},{"actual":[[["y",null]],[["y",null]]],"check":"delete from a smaller writer still wins the tie","expected":[[],[]],"passed":false},{"actual":[[["z","zb"]],[["z","zb"]]],"check":"writer breaks ties between puts","expected":[[["z","zb"]],[["z","zb"]]],"passed":true},{"actual":[[["m",1],["n",null]],[["m",1],["n",null]]],"check":"null values are real values","expected":[[["m",1],["n",null]],[["m",1],["n",null]]],"passed":true},{"actual":[[["w",null]],[["w",null]]],"check":"tombstone propagates without a prior put","expected":[[],[]],"passed":false},{"actual":[[["k0",0],["k1",1]],[["k0",0],["k1",1],["q","bq"]]],"check":"independent keys merge","expected":[[["k0",0],["k1",1]],[["k0",0],["k1",1],["q","bq"]]],"passed":true}],"passed":false,"stderr":"","stdout":"{\"observations\": [{\"check\": \"delete then stale put via merge stays deleted\", \"actual\": [[[\"k\", null]], [[\"k\", null]]], \"expected\": [[], []], \"passed\": false}, {\"check\": \"late local put older than a delete is ignored\", \"actual\": [[[\"x\", null]], []], \"expected\": [[], []], \"passed\": false}, {\"check\": \"newer put after delete revives the key\", \"actual\": [[[\"x\", \"q\"]], [[\"x\", \"q\"]]], \"expected\": [[[\"x\", \"q\"]], [[\"x\", \"q\"]]], \"passed\": true}, {\"check\": \"delete wins a timestamp tie\", \"actual\": [[[\"y\", null]], [[\"y\", null]]], \"expected\": [[], []], \"passed\": false}, {\"check\": \"delete from a smaller writer still wins the tie\", \"actual\": [[[\"y\", null]], [[\"y\", null]]], \"expected\": [[], []], \"passed\": false}, {\"check\": \"writer breaks ties between puts\", \"actual\": [[[\"z\", \"zb\"]], [[\"z\", \"zb\"]]], \"expected\": [[[\"z\", \"zb\"]], [[\"z\", \"zb\"]]], \"passed\": true}, {\"check\": \"null values are real values\", \"actual\": [[[\"m\", 1], [\"n\", null]], [[\"m\", 1], [\"n\", null]]], \"expected\": [[[\"m\", 1], [\"n\", null]], [[\"m\", 1], [\"n\", null]]], \"passed\": true}, {\"check\": \"tombstone propagates without a prior put\", \"actual\": [[[\"w\", null]], [[\"w\", null]]], \"expected\": [[], []], \"passed\": false}, {\"check\": \"independent keys merge\", \"actual\": [[[\"k0\", 0], [\"k1\", 1]], [[\"k0\", 0], [\"k1\", 1], [\"q\", \"bq\"]]], \"expected\": [[[\"k0\", 0], [\"k1\", 1]], [[\"k0\", 0], [\"k1\", 1], [\"q\", \"bq\"]]], \"passed\": true}], \"passed\": false}\n"}},"member_only":{"stages":["fixed"],"fields":["implementations.fixed","verification.fixed","harness","repair"],"note":"The verified repair, its recorded checks, the repair description, and the scoring harness are available to members."}}