FA-46746 / Bounded deques / Open access
Deque transaction accepts a snapshot from a future epoch · case 01
Deque transaction accepts a snapshot from a future epoch.
ROOT CAUSE
Deque transaction accepts a snapshot from a future epoch.
VERIFIED REPAIR
Restore the documented captured version 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(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 | [[2], 2, 2, 'committed', [1]] | [[1], 1, 3, 'conflict', []] | Failed |
SHA-256 / 074b9d70fb9f017f996f3a30ac791a9a40bad3e07f3f850436f695412332f896
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 or (saved>epoch and not a):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 | [[2], 2, 2, 'committed', [1]] | [[1], 1, 3, 'conflict', []] | Failed |
SHA-256 / 671370b6ebaeb974626e0cd885ddd1fe3b6fa9cde030c2362cc5f7ada0c1b8d9
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.032541+00:00.
Case digest / 77ca5bf17fad7967d6790fc9bdbbc7df6c3c3b7af8e4e48fa2731358dbb76443