FA-106 / Distributed coordination / Open access
Out-of-order delivery permanently loses a dependent update · case 01
A message whose prerequisites arrive later is dropped or never revisited after another pending message becomes ready.
ROOT CAUSE
Readiness is evaluated only at arrival or in one pass, instead of draining the dependency buffer to a fixed point.
VERIFIED REPAIR
Keep unresolved messages and repeatedly apply ready entries until no further progress is possible.
Unsuccessful approach: A single buffer sweep can leave a chain pending because its earlier entries become ready only after the sweep passes them.
Case contract
Initial IDs are already applied. Deliveries are [ID,dependency IDs], with duplicate IDs denoting the same operation. Apply an ID only after all dependencies are applied. Return sorted applied and pending IDs after exhausting all currently satisfiable dependencies; missing dependencies and cycles remain pending. Payload conflict resolution is outside this model.
Why this case matters
Models causal message admission over reordered delivery, including transitive unlocks, replayed deliveries and permanently unavailable prerequisites.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(initial, deliveries):
applied = set(initial)
for identity, dependencies in deliveries:
if set(dependencies) <= applied:
applied.add(identity)
return [sorted(applied), []]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
ids = ['op-'+str(i) for i in range(N+3)]
chain = [[identity, [ids[i-1]] if i else []] for i, identity in enumerate(ids)]
check('reverse dependency chain', solve([], list(reversed(chain))), [sorted(ids), []])
check('already causal arrival', solve([], chain), [sorted(ids), []])
check('missing prerequisite retained', solve([], [['waiting', ['absent']]]), [[], ['waiting']])
check('initial context unlocks delivery', solve(['root'], [['child', ['root']]]), [['child', 'root'], []])
check('dependency cycle stays pending', solve([], [['a', ['b']], ['b', ['a']]]), [[], ['a', 'b']])
check('replayed delivery', solve([], chain+chain), [sorted(ids), []])
check('empty delivery', solve(['root'], []), [['root'], []])
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 |
|---|---|---|---|
| reverse dependency chain | [['op-0'], []] | [['op-0', 'op-1', 'op-2', 'op-3'], []] | Failed |
| already causal arrival | [['op-0', 'op-1', 'op-2', 'op-3'], []] | [['op-0', 'op-1', 'op-2', 'op-3'], []] | Passed |
| missing prerequisite retained | [[], []] | [[], ['waiting']] | Failed |
| initial context unlocks delivery | [['child', 'root'], []] | [['child', 'root'], []] | Passed |
| dependency cycle stays pending | [[], []] | [[], ['a', 'b']] | Failed |
| replayed delivery | [['op-0', 'op-1', 'op-2', 'op-3'], []] | [['op-0', 'op-1', 'op-2', 'op-3'], []] | Passed |
| empty delivery | [['root'], []] | [['root'], []] | Passed |
SHA-256 / 7033e4e40fd7fdca3444e83f724c8de313a01b28cbeffa0509be3e8ae16e170c
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(initial, deliveries):
applied = set(initial)
pending = {identity: set(dependencies) for identity, dependencies in deliveries if identity not in applied}
for identity, dependencies in list(pending.items()):
if dependencies <= applied:
applied.add(identity)
del pending[identity]
return [sorted(applied), sorted(pending)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
ids = ['op-'+str(i) for i in range(N+3)]
chain = [[identity, [ids[i-1]] if i else []] for i, identity in enumerate(ids)]
check('reverse dependency chain', solve([], list(reversed(chain))), [sorted(ids), []])
check('already causal arrival', solve([], chain), [sorted(ids), []])
check('missing prerequisite retained', solve([], [['waiting', ['absent']]]), [[], ['waiting']])
check('initial context unlocks delivery', solve(['root'], [['child', ['root']]]), [['child', 'root'], []])
check('dependency cycle stays pending', solve([], [['a', ['b']], ['b', ['a']]]), [[], ['a', 'b']])
check('replayed delivery', solve([], chain+chain), [sorted(ids), []])
check('empty delivery', solve(['root'], []), [['root'], []])
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 |
|---|---|---|---|
| reverse dependency chain | [['op-0'], ['op-1', 'op-2', 'op-3']] | [['op-0', 'op-1', 'op-2', 'op-3'], []] | Failed |
| already causal arrival | [['op-0', 'op-1', 'op-2', 'op-3'], []] | [['op-0', 'op-1', 'op-2', 'op-3'], []] | Passed |
| missing prerequisite retained | [[], ['waiting']] | [[], ['waiting']] | Passed |
| initial context unlocks delivery | [['child', 'root'], []] | [['child', 'root'], []] | Passed |
| dependency cycle stays pending | [[], ['a', 'b']] | [[], ['a', 'b']] | Passed |
| replayed delivery | [['op-0', 'op-1', 'op-2', 'op-3'], []] | [['op-0', 'op-1', 'op-2', 'op-3'], []] | Passed |
| empty delivery | [['root'], []] | [['root'], []] | Passed |
SHA-256 / b016456cf64a3816d21039cc269d1fe0256eaef8f2d9a82067ec9afb82c8ad11
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(initial, deliveries):
applied = set(initial)
pending = {identity: set(dependencies) for identity, dependencies in deliveries if identity not in applied}
while pending:
ready = [identity for identity, dependencies in pending.items() if dependencies <= applied]
if not ready:
break
for identity in ready:
applied.add(identity)
del pending[identity]
return [sorted(applied), sorted(pending)]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
ids = ['op-'+str(i) for i in range(N+3)]
chain = [[identity, [ids[i-1]] if i else []] for i, identity in enumerate(ids)]
check('reverse dependency chain', solve([], list(reversed(chain))), [sorted(ids), []])
check('already causal arrival', solve([], chain), [sorted(ids), []])
check('missing prerequisite retained', solve([], [['waiting', ['absent']]]), [[], ['waiting']])
check('initial context unlocks delivery', solve(['root'], [['child', ['root']]]), [['child', 'root'], []])
check('dependency cycle stays pending', solve([], [['a', ['b']], ['b', ['a']]]), [[], ['a', 'b']])
check('replayed delivery', solve([], chain+chain), [sorted(ids), []])
check('empty delivery', solve(['root'], []), [['root'], []])
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 |
|---|---|---|---|
| reverse dependency chain | [['op-0', 'op-1', 'op-2', 'op-3'], []] | [['op-0', 'op-1', 'op-2', 'op-3'], []] | Passed |
| already causal arrival | [['op-0', 'op-1', 'op-2', 'op-3'], []] | [['op-0', 'op-1', 'op-2', 'op-3'], []] | Passed |
| missing prerequisite retained | [[], ['waiting']] | [[], ['waiting']] | Passed |
| initial context unlocks delivery | [['child', 'root'], []] | [['child', 'root'], []] | Passed |
| dependency cycle stays pending | [[], ['a', 'b']] | [[], ['a', 'b']] | Passed |
| replayed delivery | [['op-0', 'op-1', 'op-2', 'op-3'], []] | [['op-0', 'op-1', 'op-2', 'op-3'], []] | Passed |
| empty delivery | [['root'], []] | [['root'], []] | Passed |
SHA-256 / 645feb364e4b9fc3e15c19d361ff2e1560e929bde1c7d418be1d96fccb8a7d52
Verification & scope
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:36:50.462840+00:00.
Case digest / ea20422576fc10e0fa4156bc505735d5477886e4c2985f33c4fa6ad29759fbd5