FA-47211 / Bounded deques / Open access

Deque rollback counts journal writes as restored occupancy · case 01

Deque rollback counts journal writes as restored occupancy.

Verified by executionVariant 1 · 6 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

Deque rollback counts journal writes as restored occupancy.

VERIFIED REPAIR

Restore the documented size before image invariant in mutation-rollback.

Unsuccessful approach: The partial repair still applies the incorrect transition to an admitted boundary or multi-element case.

Case contract

Undo a failed bounded ring mutation from a before-image journal. Replay writes newest-first, restore captured head/size/epoch, release reserved capacity, reclaim newly allocated blocks newest-first and consume the journal.

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):
    slots,journal,old_head,old_size,old_epoch,reserved,created=x
    restored=slots[:]
    for index,value in reversed(journal):restored[index]=value
    head=old_head
    size=len(journal)
    epoch=old_epoch
    permits=0
    reclaimed=created[::-1]
    remaining=[]
    return [restored,head,size,epoch,permits,reclaimed,remaining]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N+2,None],[[0,N],[0,N+1]],1,1,3,2,[4,5]]), {1: [[1, None], 1, 1, 3, 0, [5, 4], []], 2: [[2, None], 1, 1, 3, 0, [5, 4], []], 3: [[3, None], 1, 1, 3, 0, [5, 4], []], 4: [[4, None], 1, 1, 3, 0, [5, 4], []], 5: [[5, None], 1, 1, 3, 0, [5, 4], []]}[N])
check('1', solve([[N,N+1,N+2],[[1,None],[2,None]],0,1,2,1,[7]]), {1: [[1, None, None], 0, 1, 2, 0, [7], []], 2: [[2, None, None], 0, 1, 2, 0, [7], []], 3: [[3, None, None], 0, 1, 2, 0, [7], []], 4: [[4, None, None], 0, 1, 2, 0, [7], []], 5: [[5, None, None], 0, 1, 2, 0, [7], []]}[N])
check('2', solve([[N],[],0,1,4,0,[]]), {1: [[1], 0, 1, 4, 0, [], []], 2: [[2], 0, 1, 4, 0, [], []], 3: [[3], 0, 1, 4, 0, [], []], 4: [[4], 0, 1, 4, 0, [], []], 5: [[5], 0, 1, 4, 0, [], []]}[N])
check('3', solve([[None,N+1,None],[[1,N]],1,1,0,1,[8,9,10]]), {1: [[None, 1, None], 1, 1, 0, 0, [10, 9, 8], []], 2: [[None, 2, None], 1, 1, 0, 0, [10, 9, 8], []], 3: [[None, 3, None], 1, 1, 0, 0, [10, 9, 8], []], 4: [[None, 4, None], 1, 1, 0, 0, [10, 9, 8], []], 5: [[None, 5, None], 1, 1, 0, 0, [10, 9, 8], []]}[N])
check('4', solve([[N,N+1],[[0,None],[1,None]],1,0,2,2,[3,6]]), {1: [[None, None], 1, 0, 2, 0, [6, 3], []], 2: [[None, None], 1, 0, 2, 0, [6, 3], []], 3: [[None, None], 1, 0, 2, 0, [6, 3], []], 4: [[None, None], 1, 0, 2, 0, [6, 3], []], 5: [[None, None], 1, 0, 2, 0, [6, 3], []]}[N])
check('5', solve([[N+3,N+1],[[0,N],[0,N+2]],0,2,7,3,[4,7]]), {1: [[1, 2], 0, 2, 7, 0, [7, 4], []], 2: [[2, 3], 0, 2, 7, 0, [7, 4], []], 3: [[3, 4], 0, 2, 7, 0, [7, 4], []], 4: [[4, 5], 0, 2, 7, 0, [7, 4], []], 5: [[5, 6], 0, 2, 7, 0, [7, 4], []]}[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	`[[1, None], 1, 2, 3, 0, [5, 4], []]`	`[[1, None], 1, 1, 3, 0, [5, 4], []]`	Failed
1	`[[1, None, None], 0, 2, 2, 0, [7], []]`	`[[1, None, None], 0, 1, 2, 0, [7], []]`	Failed
2	`[[1], 0, 0, 4, 0, [], []]`	`[[1], 0, 1, 4, 0, [], []]`	Failed
3	`[[None, 1, None], 1, 1, 0, 0, [10, 9, 8], []]`	`[[None, 1, None], 1, 1, 0, 0, [10, 9, 8], []]`	Passed
4	`[[None, None], 1, 2, 2, 0, [6, 3], []]`	`[[None, None], 1, 0, 2, 0, [6, 3], []]`	Failed
5	`[[1, 2], 0, 2, 7, 0, [7, 4], []]`	`[[1, 2], 0, 2, 7, 0, [7, 4], []]`	Passed

SHA-256 / ae177606cf5ac5b21b4987be412a12ca0a9e71ae25ad0c1d8ca2d7eaabe96d40

2 / The unsuccessful fix

Exit 1

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    slots,journal,old_head,old_size,old_epoch,reserved,created=x
    restored=slots[:]
    for index,value in reversed(journal):restored[index]=value
    head=old_head
    size=old_size if not journal else len(journal)
    epoch=old_epoch
    permits=0
    reclaimed=created[::-1]
    remaining=[]
    return [restored,head,size,epoch,permits,reclaimed,remaining]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N+2,None],[[0,N],[0,N+1]],1,1,3,2,[4,5]]), {1: [[1, None], 1, 1, 3, 0, [5, 4], []], 2: [[2, None], 1, 1, 3, 0, [5, 4], []], 3: [[3, None], 1, 1, 3, 0, [5, 4], []], 4: [[4, None], 1, 1, 3, 0, [5, 4], []], 5: [[5, None], 1, 1, 3, 0, [5, 4], []]}[N])
check('1', solve([[N,N+1,N+2],[[1,None],[2,None]],0,1,2,1,[7]]), {1: [[1, None, None], 0, 1, 2, 0, [7], []], 2: [[2, None, None], 0, 1, 2, 0, [7], []], 3: [[3, None, None], 0, 1, 2, 0, [7], []], 4: [[4, None, None], 0, 1, 2, 0, [7], []], 5: [[5, None, None], 0, 1, 2, 0, [7], []]}[N])
check('2', solve([[N],[],0,1,4,0,[]]), {1: [[1], 0, 1, 4, 0, [], []], 2: [[2], 0, 1, 4, 0, [], []], 3: [[3], 0, 1, 4, 0, [], []], 4: [[4], 0, 1, 4, 0, [], []], 5: [[5], 0, 1, 4, 0, [], []]}[N])
check('3', solve([[None,N+1,None],[[1,N]],1,1,0,1,[8,9,10]]), {1: [[None, 1, None], 1, 1, 0, 0, [10, 9, 8], []], 2: [[None, 2, None], 1, 1, 0, 0, [10, 9, 8], []], 3: [[None, 3, None], 1, 1, 0, 0, [10, 9, 8], []], 4: [[None, 4, None], 1, 1, 0, 0, [10, 9, 8], []], 5: [[None, 5, None], 1, 1, 0, 0, [10, 9, 8], []]}[N])
check('4', solve([[N,N+1],[[0,None],[1,None]],1,0,2,2,[3,6]]), {1: [[None, None], 1, 0, 2, 0, [6, 3], []], 2: [[None, None], 1, 0, 2, 0, [6, 3], []], 3: [[None, None], 1, 0, 2, 0, [6, 3], []], 4: [[None, None], 1, 0, 2, 0, [6, 3], []], 5: [[None, None], 1, 0, 2, 0, [6, 3], []]}[N])
check('5', solve([[N+3,N+1],[[0,N],[0,N+2]],0,2,7,3,[4,7]]), {1: [[1, 2], 0, 2, 7, 0, [7, 4], []], 2: [[2, 3], 0, 2, 7, 0, [7, 4], []], 3: [[3, 4], 0, 2, 7, 0, [7, 4], []], 4: [[4, 5], 0, 2, 7, 0, [7, 4], []], 5: [[5, 6], 0, 2, 7, 0, [7, 4], []]}[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	`[[1, None], 1, 2, 3, 0, [5, 4], []]`	`[[1, None], 1, 1, 3, 0, [5, 4], []]`	Failed
1	`[[1, None, None], 0, 2, 2, 0, [7], []]`	`[[1, None, None], 0, 1, 2, 0, [7], []]`	Failed
2	`[[1], 0, 1, 4, 0, [], []]`	`[[1], 0, 1, 4, 0, [], []]`	Passed
3	`[[None, 1, None], 1, 1, 0, 0, [10, 9, 8], []]`	`[[None, 1, None], 1, 1, 0, 0, [10, 9, 8], []]`	Passed
4	`[[None, None], 1, 2, 2, 0, [6, 3], []]`	`[[None, None], 1, 0, 2, 0, [6, 3], []]`	Failed
5	`[[1, 2], 0, 2, 7, 0, [7, 4], []]`	`[[1, 2], 0, 2, 7, 0, [7, 4], []]`	Passed

SHA-256 / d728a99e6d4488c8804bb7ddbb0cfcec220910d9f3e05ac9a53f09f53a7c61ee

3 / The verified repair

Exit 0

"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(x):
    slots,journal,old_head,old_size,old_epoch,reserved,created=x
    restored=slots[:]
    for index,value in reversed(journal):restored[index]=value
    head=old_head
    size=old_size
    epoch=old_epoch
    permits=0
    reclaimed=created[::-1]
    remaining=[]
    return [restored,head,size,epoch,permits,reclaimed,remaining]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('0', solve([[N+2,None],[[0,N],[0,N+1]],1,1,3,2,[4,5]]), {1: [[1, None], 1, 1, 3, 0, [5, 4], []], 2: [[2, None], 1, 1, 3, 0, [5, 4], []], 3: [[3, None], 1, 1, 3, 0, [5, 4], []], 4: [[4, None], 1, 1, 3, 0, [5, 4], []], 5: [[5, None], 1, 1, 3, 0, [5, 4], []]}[N])
check('1', solve([[N,N+1,N+2],[[1,None],[2,None]],0,1,2,1,[7]]), {1: [[1, None, None], 0, 1, 2, 0, [7], []], 2: [[2, None, None], 0, 1, 2, 0, [7], []], 3: [[3, None, None], 0, 1, 2, 0, [7], []], 4: [[4, None, None], 0, 1, 2, 0, [7], []], 5: [[5, None, None], 0, 1, 2, 0, [7], []]}[N])
check('2', solve([[N],[],0,1,4,0,[]]), {1: [[1], 0, 1, 4, 0, [], []], 2: [[2], 0, 1, 4, 0, [], []], 3: [[3], 0, 1, 4, 0, [], []], 4: [[4], 0, 1, 4, 0, [], []], 5: [[5], 0, 1, 4, 0, [], []]}[N])
check('3', solve([[None,N+1,None],[[1,N]],1,1,0,1,[8,9,10]]), {1: [[None, 1, None], 1, 1, 0, 0, [10, 9, 8], []], 2: [[None, 2, None], 1, 1, 0, 0, [10, 9, 8], []], 3: [[None, 3, None], 1, 1, 0, 0, [10, 9, 8], []], 4: [[None, 4, None], 1, 1, 0, 0, [10, 9, 8], []], 5: [[None, 5, None], 1, 1, 0, 0, [10, 9, 8], []]}[N])
check('4', solve([[N,N+1],[[0,None],[1,None]],1,0,2,2,[3,6]]), {1: [[None, None], 1, 0, 2, 0, [6, 3], []], 2: [[None, None], 1, 0, 2, 0, [6, 3], []], 3: [[None, None], 1, 0, 2, 0, [6, 3], []], 4: [[None, None], 1, 0, 2, 0, [6, 3], []], 5: [[None, None], 1, 0, 2, 0, [6, 3], []]}[N])
check('5', solve([[N+3,N+1],[[0,N],[0,N+2]],0,2,7,3,[4,7]]), {1: [[1, 2], 0, 2, 7, 0, [7, 4], []], 2: [[2, 3], 0, 2, 7, 0, [7, 4], []], 3: [[3, 4], 0, 2, 7, 0, [7, 4], []], 4: [[4, 5], 0, 2, 7, 0, [7, 4], []], 5: [[5, 6], 0, 2, 7, 0, [7, 4], []]}[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	`[[1, None], 1, 1, 3, 0, [5, 4], []]`	`[[1, None], 1, 1, 3, 0, [5, 4], []]`	Passed
1	`[[1, None, None], 0, 1, 2, 0, [7], []]`	`[[1, None, None], 0, 1, 2, 0, [7], []]`	Passed
2	`[[1], 0, 1, 4, 0, [], []]`	`[[1], 0, 1, 4, 0, [], []]`	Passed
3	`[[None, 1, None], 1, 1, 0, 0, [10, 9, 8], []]`	`[[None, 1, None], 1, 1, 0, 0, [10, 9, 8], []]`	Passed
4	`[[None, None], 1, 0, 2, 0, [6, 3], []]`	`[[None, None], 1, 0, 2, 0, [6, 3], []]`	Passed
5	`[[1, 2], 0, 2, 7, 0, [7, 4], []]`	`[[1, 2], 0, 2, 7, 0, [7, 4], []]`	Passed

SHA-256 / 02415cca25c95fcb919451d53a2274923d681c8b60a42d385a95ebb70b03d358

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:39.334457+00:00.

Case digest / a8b99bbf0239facb1020d472d785e8e0be180b5646fcefcaca4352a1d8795caa