FA-46771 / Bounded deques / Open access
Deque transaction charges staged entries rather than allocation cost · case 01
Deque transaction charges staged entries rather than allocation cost.
ROOT CAUSE
Deque transaction charges staged entries rather than allocation cost.
VERIFIED REPAIR
Restore the documented credit charge 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-len(staged)
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, 2, 'committed', [1, 2]] | [[3], 6, 0, 'committed', [1, 2]] | Failed |
| 6 | [[1], 1, 3, 'conflict', []] | [[1], 1, 3, 'conflict', []] | Passed |
SHA-256 / ab92170fd7c6663c9e4290245bec05e37566b2e9b894133daff04c86134bbd68
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:return [a,epoch,credits,'capacity',[]]
if cost>credits:return [a,epoch,credits,'allocation',[]]
state=staged[:]
version=epoch+1
balance=credits-cost if cost==0 else credits-len(staged)
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, 2, 'committed', [1, 2]] | [[3], 6, 0, 'committed', [1, 2]] | Failed |
| 6 | [[1], 1, 3, 'conflict', []] | [[1], 1, 3, 'conflict', []] | Passed |
SHA-256 / 95e3ca87055d43ec29f5c92969cbffdfcc1c678f8924d7afd4f6d7893de3a05c
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.225642+00:00.
Case digest / d6a8ade12e8a45b8ae80ed2b52714fc14293f101b4942c9364e1c02c468e918f