FA-74911 / CRDT convergence / Open access
LWW element set with add bias: equal add and remove timestamps hide the element · case 01
An element added and removed at the same timestamp disappears, contrary to the add-wins tie rule.
ROOT CAUSE
Membership requires the add timestamp to be strictly newer than the remove timestamp.
VERIFIED REPAIR
Treat an element as present when its add timestamp is greater than or equal to its remove timestamp.
Unsuccessful approach: Dropping a local remove that ties the local add still hides the element when the tie arrives through merge.
Case contract
Each replica keeps add and remove timestamp maps. ["add"|"rem", r, e, t] records t when it exceeds the stored timestamp. ["merge", s, d] folds both maps of s into d by maximum. An element is a member when it has an add timestamp that is greater than or equal to its remove timestamp (ties favour add). Return sorted members per replica.
Why this case matters
LWW element sets resolve add/remove races by timestamp and need a deterministic tie bias.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
A = {r: {} for r in replicas}
R = {r: {} for r in replicas}
for op in ops:
if op[0] == 'merge':
s, d = op[1], op[2]
for src, dst in ((A[s], A[d]), (R[s], R[d])):
for e, t in src.items():
if t > dst.get(e, -1):
dst[e] = t
else:
kind, r, e, t = op
table = A[r] if kind == 'add' else R[r]
if t > table.get(e, -1):
table[e] = t
def members(r):
return sorted(e for e, t in A[r].items() if t > R[r].get(e, -1))
return [members(r) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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 |
|---|---|---|---|
| add and remove at the same timestamp keep the element | [[], []] | [['x'], []] | Failed |
| tie arriving through merge keeps the element | [[], []] | [['x'], ['x']] | Failed |
| newer remove hides the element everywhere | [[], []] | [[], []] | Passed |
| older merged add does not lower the timestamp | [['z'], []] | [['z'], []] | Passed |
| out-of-order local add keeps the maximum | [['w'], []] | [['w'], []] | Passed |
| first add seen does not pin the timestamp | [['q'], ['q']] | [['q'], ['q']] | Passed |
| later local add supersedes an earlier one | [['u'], []] | [['u'], []] | Passed |
| merge only pushes from source | [['k'], ['k', 'm']] | [['k'], ['k', 'm']] | Passed |
| removes propagate without adds | [[], []] | [[], []] | Passed |
SHA-256 / 4debed7dcc3420528dc342423c075f3730c09c94bdc0270e74d91abd4e218a0d
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
A = {r: {} for r in replicas}
R = {r: {} for r in replicas}
for op in ops:
if op[0] == 'merge':
s, d = op[1], op[2]
for src, dst in ((A[s], A[d]), (R[s], R[d])):
for e, t in src.items():
if t > dst.get(e, -1):
dst[e] = t
else:
kind, r, e, t = op
if kind == 'rem' and A[r].get(e) == t:
continue
table = A[r] if kind == 'add' else R[r]
if t > table.get(e, -1):
table[e] = t
def members(r):
return sorted(e for e, t in A[r].items() if t > R[r].get(e, -1))
return [members(r) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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 |
|---|---|---|---|
| add and remove at the same timestamp keep the element | [['x'], []] | [['x'], []] | Passed |
| tie arriving through merge keeps the element | [[], []] | [['x'], ['x']] | Failed |
| newer remove hides the element everywhere | [[], []] | [[], []] | Passed |
| older merged add does not lower the timestamp | [['z'], []] | [['z'], []] | Passed |
| out-of-order local add keeps the maximum | [['w'], []] | [['w'], []] | Passed |
| first add seen does not pin the timestamp | [['q'], ['q']] | [['q'], ['q']] | Passed |
| later local add supersedes an earlier one | [['u'], []] | [['u'], []] | Passed |
| merge only pushes from source | [['k'], ['k', 'm']] | [['k'], ['k', 'm']] | Passed |
| removes propagate without adds | [[], []] | [[], []] | Passed |
SHA-256 / 004f08f33166d34842ee54cb209bdba473427d376f51cad7edb6a9c791bb52d0
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(ops, replicas):
A = {r: {} for r in replicas}
R = {r: {} for r in replicas}
for op in ops:
if op[0] == 'merge':
s, d = op[1], op[2]
for src, dst in ((A[s], A[d]), (R[s], R[d])):
for e, t in src.items():
if t > dst.get(e, -1):
dst[e] = t
else:
kind, r, e, t = op
table = A[r] if kind == 'add' else R[r]
if t > table.get(e, -1):
table[e] = t
def members(r):
return sorted(e for e, t in A[r].items() if t >= R[r].get(e, -1))
return [members(r) for r in replicas]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = {
1: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 1], ['rem', 'a', 'x', 1]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 2], ['rem', 'b', 'x', 2], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 2], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 6], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 3], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 5], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 4], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 5], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 1], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 2], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
2: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 2], ['rem', 'a', 'x', 2]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 3], ['rem', 'b', 'x', 3], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 3], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 7], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 4], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 6], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 5], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 6], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 2], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 3], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
3: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 3], ['rem', 'a', 'x', 3]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 4], ['rem', 'b', 'x', 4], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 4], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 8], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 5], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 7], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 6], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 7], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 3], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 4], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
4: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 4], ['rem', 'a', 'x', 4]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 5], ['rem', 'b', 'x', 5], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 5], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 9], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 6], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 8], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 7], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 8], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 4], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 5], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
5: [('add and remove at the same timestamp keep the element', [[['add', 'a', 'x', 5], ['rem', 'a', 'x', 5]], ['a', 'b']], [['x'], []]), ('tie arriving through merge keeps the element', [[['add', 'a', 'x', 6], ['rem', 'b', 'x', 6], ['merge', 'b', 'a'], ['merge', 'a', 'b']], ['a', 'b']], [['x'], ['x']]), ('newer remove hides the element everywhere', [[['add', 'a', 'y', 1], ['merge', 'a', 'b'], ['rem', 'b', 'y', 6], ['merge', 'b', 'a']], ['a', 'b']], [[], []]), ('older merged add does not lower the timestamp', [[['add', 'a', 'z', 10], ['add', 'b', 'z', 1], ['rem', 'b', 'z', 7], ['merge', 'b', 'a']], ['a', 'b']], [['z'], []]), ('out-of-order local add keeps the maximum', [[['add', 'a', 'w', 9], ['add', 'a', 'w', 2], ['rem', 'a', 'w', 3]], ['a', 'b']], [['w'], []]), ('first add seen does not pin the timestamp', [[['add', 'b', 'q', 1], ['rem', 'a', 'q', 2], ['add', 'a', 'q', 8], ['merge', 'a', 'b'], ['merge', 'b', 'a']], ['a', 'b']], [['q'], ['q']]), ('later local add supersedes an earlier one', [[['add', 'a', 'u', 1], ['add', 'a', 'u', 9], ['rem', 'a', 'u', 3]], ['a', 'b']], [['u'], []]), ('merge only pushes from source', [[['add', 'a', 'k', 1], ['add', 'b', 'm', 5], ['merge', 'a', 'b']], ['a', 'b']], [['k'], ['k', 'm']]), ('removes propagate without adds', [[['add', 'a', 'v', 1], ['add', 'b', 'v', 1], ['rem', 'a', 'v', 6], ['merge', 'a', 'b']], ['a', 'b']], [[], []])],
}[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 |
|---|---|---|---|
| add and remove at the same timestamp keep the element | [['x'], []] | [['x'], []] | Passed |
| tie arriving through merge keeps the element | [['x'], ['x']] | [['x'], ['x']] | Passed |
| newer remove hides the element everywhere | [[], []] | [[], []] | Passed |
| older merged add does not lower the timestamp | [['z'], []] | [['z'], []] | Passed |
| out-of-order local add keeps the maximum | [['w'], []] | [['w'], []] | Passed |
| first add seen does not pin the timestamp | [['q'], ['q']] | [['q'], ['q']] | Passed |
| later local add supersedes an earlier one | [['u'], []] | [['u'], []] | Passed |
| merge only pushes from source | [['k'], ['k', 'm']] | [['k'], ['k', 'm']] | Passed |
| removes propagate without adds | [[], []] | [[], []] | Passed |
SHA-256 / dfc95ba445a038b2aabfdf160543c263f7233e9bccc8bd7cbab3bb6c5cc468ec
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:01.053960+00:00.
Case digest / e4297adb427c62bc410e7e2e053198c8f9ccc4aa788c9e93c6c819ab3fe53599