FA-46751 / Bounded deques / Open access
Deque transaction validates old rather than staged occupancy · case 01
Deque transaction validates old rather than staged occupancy.
ROOT CAUSE
Deque transaction validates old rather than staged occupancy.
VERIFIED REPAIR
Restore the documented staged size invariant in transaction-publish.
Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.
Case contract
Publish a complete staged bounded deque only if its captured epoch matches, its occupancy fits and allocation credits suffice. Failure preserves state, epoch and credits; success retires the old snapshot.
Why this case matters
Controlled bounded deque implementation model with explicit storage and lifecycle observations.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
a,staged,cap,epoch,saved,cost,credits=x
if saved!=epoch:return [a,epoch,credits,'conflict',[]]
if len(a)>cap:return [a,epoch,credits,'capacity',[]]
if cost>credits:return [a,epoch,credits,'allocation',[]]
state=staged[:]
version=epoch+1
balance=credits-cost
retired=a[:]
return [state,version,balance,'committed',retired]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N],[N+1,N+2],3,2,2,2,5]), {1: [[2, 3], 3, 3, 'committed', [1]], 2: [[3, 4], 3, 3, 'committed', [2]], 3: [[4, 5], 3, 3, 'committed', [3]], 4: [[5, 6], 3, 3, 'committed', [4]], 5: [[6, 7], 3, 3, 'committed', [5]]}[N])
check('1', solve([[N],[N+1],3,3,2,1,4]), {1: [[1], 3, 4, 'conflict', []], 2: [[2], 3, 4, 'conflict', []], 3: [[3], 3, 4, 'conflict', []], 4: [[4], 3, 4, 'conflict', []], 5: [[5], 3, 4, 'conflict', []]}[N])
check('2', solve([[N],[N+1,N+2,N+3],2,4,4,1,3]), {1: [[1], 4, 3, 'capacity', []], 2: [[2], 4, 3, 'capacity', []], 3: [[3], 4, 3, 'capacity', []], 4: [[4], 4, 3, 'capacity', []], 5: [[5], 4, 3, 'capacity', []]}[N])
check('3', solve([[N],[N+1],2,1,1,4,2]), {1: [[1], 1, 2, 'allocation', []], 2: [[2], 1, 2, 'allocation', []], 3: [[3], 1, 2, 'allocation', []], 4: [[4], 1, 2, 'allocation', []], 5: [[5], 1, 2, 'allocation', []]}[N])
check('4', solve([[],[],0,0,0,0,0]), {1: [[], 1, 0, 'committed', []], 2: [[], 1, 0, 'committed', []], 3: [[], 1, 0, 'committed', []], 4: [[], 1, 0, 'committed', []], 5: [[], 1, 0, 'committed', []]}[N])
check('5', solve([[N,N+1],[N+2],2,5,5,3,3]), {1: [[3], 6, 0, 'committed', [1, 2]], 2: [[4], 6, 0, 'committed', [2, 3]], 3: [[5], 6, 0, 'committed', [3, 4]], 4: [[6], 6, 0, 'committed', [4, 5]], 5: [[7], 6, 0, 'committed', [5, 6]]}[N])
check('6', solve([[N],[N+1],2,1,2,1,3]), {1: [[1], 1, 3, 'conflict', []], 2: [[2], 1, 3, 'conflict', []], 3: [[3], 1, 3, 'conflict', []], 4: [[4], 1, 3, 'conflict', []], 5: [[5], 1, 3, 'conflict', []]}[N])
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 |
|---|---|---|---|
| 0 | [[2, 3], 3, 3, 'committed', [1]] | [[2, 3], 3, 3, 'committed', [1]] | Passed |
| 1 | [[1], 3, 4, 'conflict', []] | [[1], 3, 4, 'conflict', []] | Passed |
| 2 | [[2, 3, 4], 5, 2, 'committed', [1]] | [[1], 4, 3, 'capacity', []] | Failed |
| 3 | [[1], 1, 2, 'allocation', []] | [[1], 1, 2, 'allocation', []] | Passed |
| 4 | [[], 1, 0, 'committed', []] | [[], 1, 0, 'committed', []] | Passed |
| 5 | [[3], 6, 0, 'committed', [1, 2]] | [[3], 6, 0, 'committed', [1, 2]] | Passed |
| 6 | [[1], 1, 3, 'conflict', []] | [[1], 1, 3, 'conflict', []] | Passed |
SHA-256 / b6ebfb6b821eab4d58fefc2ed0ae52139ee1d288cac5cfdf9a40d44acc0221ad
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
a,staged,cap,epoch,saved,cost,credits=x
if saved!=epoch:return [a,epoch,credits,'conflict',[]]
if len(staged)>cap and not a:return [a,epoch,credits,'capacity',[]]
if cost>credits:return [a,epoch,credits,'allocation',[]]
state=staged[:]
version=epoch+1
balance=credits-cost
retired=a[:]
return [state,version,balance,'committed',retired]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N],[N+1,N+2],3,2,2,2,5]), {1: [[2, 3], 3, 3, 'committed', [1]], 2: [[3, 4], 3, 3, 'committed', [2]], 3: [[4, 5], 3, 3, 'committed', [3]], 4: [[5, 6], 3, 3, 'committed', [4]], 5: [[6, 7], 3, 3, 'committed', [5]]}[N])
check('1', solve([[N],[N+1],3,3,2,1,4]), {1: [[1], 3, 4, 'conflict', []], 2: [[2], 3, 4, 'conflict', []], 3: [[3], 3, 4, 'conflict', []], 4: [[4], 3, 4, 'conflict', []], 5: [[5], 3, 4, 'conflict', []]}[N])
check('2', solve([[N],[N+1,N+2,N+3],2,4,4,1,3]), {1: [[1], 4, 3, 'capacity', []], 2: [[2], 4, 3, 'capacity', []], 3: [[3], 4, 3, 'capacity', []], 4: [[4], 4, 3, 'capacity', []], 5: [[5], 4, 3, 'capacity', []]}[N])
check('3', solve([[N],[N+1],2,1,1,4,2]), {1: [[1], 1, 2, 'allocation', []], 2: [[2], 1, 2, 'allocation', []], 3: [[3], 1, 2, 'allocation', []], 4: [[4], 1, 2, 'allocation', []], 5: [[5], 1, 2, 'allocation', []]}[N])
check('4', solve([[],[],0,0,0,0,0]), {1: [[], 1, 0, 'committed', []], 2: [[], 1, 0, 'committed', []], 3: [[], 1, 0, 'committed', []], 4: [[], 1, 0, 'committed', []], 5: [[], 1, 0, 'committed', []]}[N])
check('5', solve([[N,N+1],[N+2],2,5,5,3,3]), {1: [[3], 6, 0, 'committed', [1, 2]], 2: [[4], 6, 0, 'committed', [2, 3]], 3: [[5], 6, 0, 'committed', [3, 4]], 4: [[6], 6, 0, 'committed', [4, 5]], 5: [[7], 6, 0, 'committed', [5, 6]]}[N])
check('6', solve([[N],[N+1],2,1,2,1,3]), {1: [[1], 1, 3, 'conflict', []], 2: [[2], 1, 3, 'conflict', []], 3: [[3], 1, 3, 'conflict', []], 4: [[4], 1, 3, 'conflict', []], 5: [[5], 1, 3, 'conflict', []]}[N])
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 |
|---|---|---|---|
| 0 | [[2, 3], 3, 3, 'committed', [1]] | [[2, 3], 3, 3, 'committed', [1]] | Passed |
| 1 | [[1], 3, 4, 'conflict', []] | [[1], 3, 4, 'conflict', []] | Passed |
| 2 | [[2, 3, 4], 5, 2, 'committed', [1]] | [[1], 4, 3, 'capacity', []] | Failed |
| 3 | [[1], 1, 2, 'allocation', []] | [[1], 1, 2, 'allocation', []] | Passed |
| 4 | [[], 1, 0, 'committed', []] | [[], 1, 0, 'committed', []] | Passed |
| 5 | [[3], 6, 0, 'committed', [1, 2]] | [[3], 6, 0, 'committed', [1, 2]] | Passed |
| 6 | [[1], 1, 3, 'conflict', []] | [[1], 1, 3, 'conflict', []] | Passed |
SHA-256 / b0b65b4f781744ef936f23b08efcd98838cce48fcaab822beb9736b6efd14fed
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
a,staged,cap,epoch,saved,cost,credits=x
if saved!=epoch:return [a,epoch,credits,'conflict',[]]
if len(staged)>cap:return [a,epoch,credits,'capacity',[]]
if cost>credits:return [a,epoch,credits,'allocation',[]]
state=staged[:]
version=epoch+1
balance=credits-cost
retired=a[:]
return [state,version,balance,'committed',retired]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N],[N+1,N+2],3,2,2,2,5]), {1: [[2, 3], 3, 3, 'committed', [1]], 2: [[3, 4], 3, 3, 'committed', [2]], 3: [[4, 5], 3, 3, 'committed', [3]], 4: [[5, 6], 3, 3, 'committed', [4]], 5: [[6, 7], 3, 3, 'committed', [5]]}[N])
check('1', solve([[N],[N+1],3,3,2,1,4]), {1: [[1], 3, 4, 'conflict', []], 2: [[2], 3, 4, 'conflict', []], 3: [[3], 3, 4, 'conflict', []], 4: [[4], 3, 4, 'conflict', []], 5: [[5], 3, 4, 'conflict', []]}[N])
check('2', solve([[N],[N+1,N+2,N+3],2,4,4,1,3]), {1: [[1], 4, 3, 'capacity', []], 2: [[2], 4, 3, 'capacity', []], 3: [[3], 4, 3, 'capacity', []], 4: [[4], 4, 3, 'capacity', []], 5: [[5], 4, 3, 'capacity', []]}[N])
check('3', solve([[N],[N+1],2,1,1,4,2]), {1: [[1], 1, 2, 'allocation', []], 2: [[2], 1, 2, 'allocation', []], 3: [[3], 1, 2, 'allocation', []], 4: [[4], 1, 2, 'allocation', []], 5: [[5], 1, 2, 'allocation', []]}[N])
check('4', solve([[],[],0,0,0,0,0]), {1: [[], 1, 0, 'committed', []], 2: [[], 1, 0, 'committed', []], 3: [[], 1, 0, 'committed', []], 4: [[], 1, 0, 'committed', []], 5: [[], 1, 0, 'committed', []]}[N])
check('5', solve([[N,N+1],[N+2],2,5,5,3,3]), {1: [[3], 6, 0, 'committed', [1, 2]], 2: [[4], 6, 0, 'committed', [2, 3]], 3: [[5], 6, 0, 'committed', [3, 4]], 4: [[6], 6, 0, 'committed', [4, 5]], 5: [[7], 6, 0, 'committed', [5, 6]]}[N])
check('6', solve([[N],[N+1],2,1,2,1,3]), {1: [[1], 1, 3, 'conflict', []], 2: [[2], 1, 3, 'conflict', []], 3: [[3], 1, 3, 'conflict', []], 4: [[4], 1, 3, 'conflict', []], 5: [[5], 1, 3, 'conflict', []]}[N])
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 |
|---|---|---|---|
| 0 | [[2, 3], 3, 3, 'committed', [1]] | [[2, 3], 3, 3, 'committed', [1]] | Passed |
| 1 | [[1], 3, 4, 'conflict', []] | [[1], 3, 4, 'conflict', []] | Passed |
| 2 | [[1], 4, 3, 'capacity', []] | [[1], 4, 3, 'capacity', []] | Passed |
| 3 | [[1], 1, 2, 'allocation', []] | [[1], 1, 2, 'allocation', []] | Passed |
| 4 | [[], 1, 0, 'committed', []] | [[], 1, 0, 'committed', []] | Passed |
| 5 | [[3], 6, 0, 'committed', [1, 2]] | [[3], 6, 0, 'committed', [1, 2]] | Passed |
| 6 | [[1], 1, 3, 'conflict', []] | [[1], 1, 3, 'conflict', []] | Passed |
SHA-256 / fe9b5f5e4839dd6f78a3f09b69a6719800291d1013fb4c6e662a32f9c59eba60
Verification & scope
Offline finite deterministic model; no claim of production implementation or concurrent memory-model conformance. 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:44:35.054682+00:00.
Case digest / 72ee83d9531d7d28bc3c874565ba3368b295eb8b0a70f02d15bc2f65f0796c07