FA-46756 / Bounded deques / Open access
Deque transaction accepts insufficient allocation credits · case 01
Deque transaction accepts insufficient allocation credits.
ROOT CAUSE
Deque transaction accepts insufficient allocation credits.
VERIFIED REPAIR
Restore the documented credit admission 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<0: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 | [[2], 2, -2, 'committed', [1]] | [[1], 1, 2, 'allocation', []] | Failed |
| 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 / 2f859b4fba247521db79130620ea734d4b89458c20e718ed5dc190ce19083116
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 and credits==0: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 | [[2], 2, -2, 'committed', [1]] | [[1], 1, 2, 'allocation', []] | Failed |
| 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 / 746afbddf43022737ad4d6b0035a44ef37a2b351e63e74f1b8204fa31b5dc9d2
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.221310+00:00.
Case digest / 20ade5f4a96e5d7c1fe6a195b021bc8529e6380743f086b47c39247793587265