FA-46136 / Bounded deques / Open access

Deadline deque retains entries at their expiry instant · case 01

Deadline deque retains entries at their expiry instant.

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

ROOT CAUSE

Deadline deque retains entries at their expiry instant.

VERIFIED REPAIR

Restore the documented equality expiry invariant in deadline-prefix.

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

Case contract

A deadline-ordered bounded deque expires the maximal prefix with deadline <= now. Return live entries, release sequence, removed count and next wake deadline.

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):
    items,now=x
    cut=0
    while cut<len(items) and items[cut][1]<now:
        cut+=1
    live=items[cut:]
    released=items[:cut]
    wake=live[0][1] if live else None
    return [live,released,cut,wake]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('deadline equality', solve([[[N,1],[N+1,3],[N+2,6]],3]), {1: [[[3, 6]], [[1, 1], [2, 3]], 2, 6], 2: [[[4, 6]], [[2, 1], [3, 3]], 2, 6], 3: [[[5, 6]], [[3, 1], [4, 3]], 2, 6], 4: [[[6, 6]], [[4, 1], [5, 3]], 2, 6], 5: [[[7, 6]], [[5, 1], [6, 3]], 2, 6]}[N])
check('all expired', solve([[[N,1],[N+1,2]],8]), {1: [[], [[1, 1], [2, 2]], 2, None], 2: [[], [[2, 1], [3, 2]], 2, None], 3: [[], [[3, 1], [4, 2]], 2, None], 4: [[], [[4, 1], [5, 2]], 2, None], 5: [[], [[5, 1], [6, 2]], 2, None]}[N])
check('none expired', solve([[[N,4],[N+1,7]],1]), {1: [[[1, 4], [2, 7]], [], 0, 4], 2: [[[2, 4], [3, 7]], [], 0, 4], 3: [[[3, 4], [4, 7]], [], 0, 4], 4: [[[4, 4], [5, 7]], [], 0, 4], 5: [[[5, 4], [6, 7]], [], 0, 4]}[N])
check('empty', solve([[],3]), {1: [[], [], 0, None], 2: [[], [], 0, None], 3: [[], [], 0, None], 4: [[], [], 0, None], 5: [[], [], 0, None]}[N])
check('same deadlines', solve([[[N,2],[N+1,2],[N+2,4]],2]), {1: [[[3, 4]], [[1, 2], [2, 2]], 2, 4], 2: [[[4, 4]], [[2, 2], [3, 2]], 2, 4], 3: [[[5, 4]], [[3, 2], [4, 2]], 2, 4], 4: [[[6, 4]], [[4, 2], [5, 2]], 2, 4], 5: [[[7, 4]], [[5, 2], [6, 2]], 2, 4]}[N])
check('one expired', solve([[[N,1],[N+1,8],[N+2,9]],4]), {1: [[[2, 8], [3, 9]], [[1, 1]], 1, 8], 2: [[[3, 8], [4, 9]], [[2, 1]], 1, 8], 3: [[[4, 8], [5, 9]], [[3, 1]], 1, 8], 4: [[[5, 8], [6, 9]], [[4, 1]], 1, 8], 5: [[[6, 8], [7, 9]], [[5, 1]], 1, 8]}[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
deadline equality	`[[[2, 3], [3, 6]], [[1, 1]], 1, 3]`	`[[[3, 6]], [[1, 1], [2, 3]], 2, 6]`	Failed
all expired	`[[], [[1, 1], [2, 2]], 2, None]`	`[[], [[1, 1], [2, 2]], 2, None]`	Passed
none expired	`[[[1, 4], [2, 7]], [], 0, 4]`	`[[[1, 4], [2, 7]], [], 0, 4]`	Passed
empty	`[[], [], 0, None]`	`[[], [], 0, None]`	Passed
same deadlines	`[[[1, 2], [2, 2], [3, 4]], [], 0, 2]`	`[[[3, 4]], [[1, 2], [2, 2]], 2, 4]`	Failed
one expired	`[[[2, 8], [3, 9]], [[1, 1]], 1, 8]`	`[[[2, 8], [3, 9]], [[1, 1]], 1, 8]`	Passed

SHA-256 / 9e45f4b5351ed216d1aa02d10c8a4fa465434f08280e7c7f85ddf675334fdca4

2 / The unsuccessful fix

Exit 1

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

N = 1
observations = []
def solve(x):
    items,now=x
    cut=0
    while cut<len(items) and (items[cut][1]<now or (cut==0 and items[cut][1]==now)):
        cut+=1
    live=items[cut:]
    released=items[:cut]
    wake=live[0][1] if live else None
    return [live,released,cut,wake]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('deadline equality', solve([[[N,1],[N+1,3],[N+2,6]],3]), {1: [[[3, 6]], [[1, 1], [2, 3]], 2, 6], 2: [[[4, 6]], [[2, 1], [3, 3]], 2, 6], 3: [[[5, 6]], [[3, 1], [4, 3]], 2, 6], 4: [[[6, 6]], [[4, 1], [5, 3]], 2, 6], 5: [[[7, 6]], [[5, 1], [6, 3]], 2, 6]}[N])
check('all expired', solve([[[N,1],[N+1,2]],8]), {1: [[], [[1, 1], [2, 2]], 2, None], 2: [[], [[2, 1], [3, 2]], 2, None], 3: [[], [[3, 1], [4, 2]], 2, None], 4: [[], [[4, 1], [5, 2]], 2, None], 5: [[], [[5, 1], [6, 2]], 2, None]}[N])
check('none expired', solve([[[N,4],[N+1,7]],1]), {1: [[[1, 4], [2, 7]], [], 0, 4], 2: [[[2, 4], [3, 7]], [], 0, 4], 3: [[[3, 4], [4, 7]], [], 0, 4], 4: [[[4, 4], [5, 7]], [], 0, 4], 5: [[[5, 4], [6, 7]], [], 0, 4]}[N])
check('empty', solve([[],3]), {1: [[], [], 0, None], 2: [[], [], 0, None], 3: [[], [], 0, None], 4: [[], [], 0, None], 5: [[], [], 0, None]}[N])
check('same deadlines', solve([[[N,2],[N+1,2],[N+2,4]],2]), {1: [[[3, 4]], [[1, 2], [2, 2]], 2, 4], 2: [[[4, 4]], [[2, 2], [3, 2]], 2, 4], 3: [[[5, 4]], [[3, 2], [4, 2]], 2, 4], 4: [[[6, 4]], [[4, 2], [5, 2]], 2, 4], 5: [[[7, 4]], [[5, 2], [6, 2]], 2, 4]}[N])
check('one expired', solve([[[N,1],[N+1,8],[N+2,9]],4]), {1: [[[2, 8], [3, 9]], [[1, 1]], 1, 8], 2: [[[3, 8], [4, 9]], [[2, 1]], 1, 8], 3: [[[4, 8], [5, 9]], [[3, 1]], 1, 8], 4: [[[5, 8], [6, 9]], [[4, 1]], 1, 8], 5: [[[6, 8], [7, 9]], [[5, 1]], 1, 8]}[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
deadline equality	`[[[2, 3], [3, 6]], [[1, 1]], 1, 3]`	`[[[3, 6]], [[1, 1], [2, 3]], 2, 6]`	Failed
all expired	`[[], [[1, 1], [2, 2]], 2, None]`	`[[], [[1, 1], [2, 2]], 2, None]`	Passed
none expired	`[[[1, 4], [2, 7]], [], 0, 4]`	`[[[1, 4], [2, 7]], [], 0, 4]`	Passed
empty	`[[], [], 0, None]`	`[[], [], 0, None]`	Passed
same deadlines	`[[[2, 2], [3, 4]], [[1, 2]], 1, 2]`	`[[[3, 4]], [[1, 2], [2, 2]], 2, 4]`	Failed
one expired	`[[[2, 8], [3, 9]], [[1, 1]], 1, 8]`	`[[[2, 8], [3, 9]], [[1, 1]], 1, 8]`	Passed

SHA-256 / c92f5903f6e13e457784c7f2ef590542bc043802bca4d1f761a1daaf6542b256

3 / The verified repair

Exit 0

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

N = 1
observations = []
def solve(x):
    items,now=x
    cut=0
    while cut<len(items) and items[cut][1]<=now:
        cut+=1
    live=items[cut:]
    released=items[:cut]
    wake=live[0][1] if live else None
    return [live,released,cut,wake]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('deadline equality', solve([[[N,1],[N+1,3],[N+2,6]],3]), {1: [[[3, 6]], [[1, 1], [2, 3]], 2, 6], 2: [[[4, 6]], [[2, 1], [3, 3]], 2, 6], 3: [[[5, 6]], [[3, 1], [4, 3]], 2, 6], 4: [[[6, 6]], [[4, 1], [5, 3]], 2, 6], 5: [[[7, 6]], [[5, 1], [6, 3]], 2, 6]}[N])
check('all expired', solve([[[N,1],[N+1,2]],8]), {1: [[], [[1, 1], [2, 2]], 2, None], 2: [[], [[2, 1], [3, 2]], 2, None], 3: [[], [[3, 1], [4, 2]], 2, None], 4: [[], [[4, 1], [5, 2]], 2, None], 5: [[], [[5, 1], [6, 2]], 2, None]}[N])
check('none expired', solve([[[N,4],[N+1,7]],1]), {1: [[[1, 4], [2, 7]], [], 0, 4], 2: [[[2, 4], [3, 7]], [], 0, 4], 3: [[[3, 4], [4, 7]], [], 0, 4], 4: [[[4, 4], [5, 7]], [], 0, 4], 5: [[[5, 4], [6, 7]], [], 0, 4]}[N])
check('empty', solve([[],3]), {1: [[], [], 0, None], 2: [[], [], 0, None], 3: [[], [], 0, None], 4: [[], [], 0, None], 5: [[], [], 0, None]}[N])
check('same deadlines', solve([[[N,2],[N+1,2],[N+2,4]],2]), {1: [[[3, 4]], [[1, 2], [2, 2]], 2, 4], 2: [[[4, 4]], [[2, 2], [3, 2]], 2, 4], 3: [[[5, 4]], [[3, 2], [4, 2]], 2, 4], 4: [[[6, 4]], [[4, 2], [5, 2]], 2, 4], 5: [[[7, 4]], [[5, 2], [6, 2]], 2, 4]}[N])
check('one expired', solve([[[N,1],[N+1,8],[N+2,9]],4]), {1: [[[2, 8], [3, 9]], [[1, 1]], 1, 8], 2: [[[3, 8], [4, 9]], [[2, 1]], 1, 8], 3: [[[4, 8], [5, 9]], [[3, 1]], 1, 8], 4: [[[5, 8], [6, 9]], [[4, 1]], 1, 8], 5: [[[6, 8], [7, 9]], [[5, 1]], 1, 8]}[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
deadline equality	`[[[3, 6]], [[1, 1], [2, 3]], 2, 6]`	`[[[3, 6]], [[1, 1], [2, 3]], 2, 6]`	Passed
all expired	`[[], [[1, 1], [2, 2]], 2, None]`	`[[], [[1, 1], [2, 2]], 2, None]`	Passed
none expired	`[[[1, 4], [2, 7]], [], 0, 4]`	`[[[1, 4], [2, 7]], [], 0, 4]`	Passed
empty	`[[], [], 0, None]`	`[[], [], 0, None]`	Passed
same deadlines	`[[[3, 4]], [[1, 2], [2, 2]], 2, 4]`	`[[[3, 4]], [[1, 2], [2, 2]], 2, 4]`	Passed
one expired	`[[[2, 8], [3, 9]], [[1, 1]], 1, 8]`	`[[[2, 8], [3, 9]], [[1, 1]], 1, 8]`	Passed

SHA-256 / a30ae0414cc22ee0d4553a1fcbbe8c64c6ffc6b96b31e9e703cdeb3c9416f2c9

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

Case digest / 4fb60a91a2cf8060216cfef3561e8fc7561a3435be88048f8ee11789b71c6742