FA-46156 / Bounded deques / Open access

Deadline deque schedules wakeup from the newest live entry · case 01

Deadline deque schedules wakeup from the newest live entry.

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

ROOT CAUSE

Deadline deque schedules wakeup from the newest live entry.

VERIFIED REPAIR

Restore the documented wake selection 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[-1][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, 7]`	`[[[1, 4], [2, 7]], [], 0, 4]`	Failed
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, 9]`	`[[[2, 8], [3, 9]], [[1, 1]], 1, 8]`	Failed

SHA-256 / cb6cdee7ced82448b37b3ec48dbb14e57936b08a304ae49f1371f9ab190c7686

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:
        cut+=1
    live=items[cut:]
    released=items[:cut]
    wake=(live[0][1] if len(live)<2 else live[-1][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, 7]`	`[[[1, 4], [2, 7]], [], 0, 4]`	Failed
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, 9]`	`[[[2, 8], [3, 9]], [[1, 1]], 1, 8]`	Failed

SHA-256 / 4aaf306d854916ba77bd6e2af97ddcc97d025fccbc5a132fc5a6c761a815315f

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

Case digest / 2d63578aec21ce54f0657353540c51268f9d2b415dccac31769371eaf78b70f5