FA-74921 / CRDT convergence / Open access
LWW element set with add bias: merge omits the remove map · case 01
Removes never reach other replicas, which keep showing deleted elements.
ROOT CAUSE
Only the add map is folded during merge.
VERIFIED REPAIR
Fold both the add map and the remove map from source to destination.
Unsuccessful approach: Folding the remove map in the reverse direction teaches the source the destination's removes but not vice versa.
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]),):
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 | [['y'], []] | [[], []] | Failed |
| 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 | [[], ['v']] | [[], []] | Failed |
SHA-256 / 4c18a7cf5ecd0b2e1b3eea3f24ceb6ee4c809410f16bc2b72340df88a4feca45
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[d], R[s])):
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 | [['y'], []] | [[], []] | Failed |
| 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 | [[], ['v']] | [[], []] | Failed |
SHA-256 / 3f18a25f908614b838afb9a9cd6193751409c0d6b522c21f7c84d75aca03efb6
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.137345+00:00.
Case digest / 6585bf7276d6e0ec5f60dd71470925687dbe30072a60cdea7d80ae0de1881e95