FA-73671 / Rate limiter algorithms / Open access
Priority limiter with reserved high-priority capacity: low traffic ignores total usage · case 01
When high traffic is heavy, low requests are still admitted and the window exceeds capacity.
ROOT CAUSE
The low-priority test checks only the low counter against the non-reserved share.
VERIFIED REPAIR
Require both low < capacity - reserve and total < capacity.
Unsuccessful approach: Comparing the total against the non-reserved share lets high traffic consume the low share.
Case contract
Input {capacity, reserved_high, requests [[t_ms, priority]]} with nondecreasing t, one-second epoch windows. Only the exact label "high" is high priority; every other label is low. A high request is admitted while total admitted < capacity. A low request is admitted only while admitted low < capacity - reserved_high and total < capacity. Both counters reset each window. Return [decisions, [low, high] of the final window].
Why this case matters
Shared limiters reserve headroom for critical traffic (health checks, payments) so that bulk clients cannot starve it; the reserve arithmetic decides whether the guarantee holds.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
cap = x['capacity']
res = x['reserved_high']
win = None
low = high = 0
out = []
for t, prio in x['requests']:
w = t // 1000
if w != win:
win, low, high = w, 0, 0
if prio == 'high':
ok = low + high < cap
else:
ok = low < cap - res
if ok:
if prio == 'high':
high += 1
else:
low += 1
out.append('allow')
else:
out.append('deny')
return [out, [low, high]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[4, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [8, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [4, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [5, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1003, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[1, 'low'],
[1, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[23, 'low'],
[30, 'batch'],
[460, 'batch'],
[783, 'low'],
[807, 'high'],
[926, 'low'],
[1133, 'low'],
[1169, 'low'],
[1221, 'high'],
[1686, 'low'],
[1702, 'low'],
[1740, 'low'],
[2424, 'low'],
[2472, 'high']],
'reserved_high': 2},
[['allow',
'allow',
'deny',
'deny',
'allow',
'deny',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'allow',
'allow'],
[1, 1]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[5, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [9, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [5, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [6, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1004, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[2, 'low'],
[2, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[284, 'batch'],
[629, 'low'],
[787, 'low'],
[903, 'low'],
[1032, 'batch'],
[1118, 'high'],
[1495, 'low'],
[1855, 'low'],
[1876, 'low'],
[1919, 'batch'],
[2238, 'high'],
[2382, 'batch'],
[2390, 'high'],
[2492, 'high']],
'reserved_high': 2},
[['allow',
'allow',
'deny',
'deny',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'allow',
'allow',
'allow',
'allow'],
[1, 3]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[6, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [10, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [6, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [7, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1005, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[3, 'low'],
[3, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[99, 'low'],
[696, 'low'],
[811, 'batch'],
[837, 'low'],
[912, 'batch'],
[1070, 'low'],
[1174, 'batch'],
[1400, 'batch'],
[1530, 'low'],
[1887, 'high'],
[1994, 'batch'],
[2235, 'low'],
[2286, 'low'],
[2369, 'high']],
'reserved_high': 2},
[['allow',
'allow',
'deny',
'deny',
'deny',
'allow',
'allow',
'deny',
'deny',
'allow',
'deny',
'allow',
'allow',
'allow'],
[2, 1]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[7, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [11, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [7, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [8, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1006, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[4, 'low'],
[4, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[279, 'high'],
[550, 'high'],
[665, 'low'],
[940, 'low'],
[1010, 'batch'],
[1022, 'low'],
[1597, 'low'],
[1623, 'batch'],
[1749, 'low'],
[1850, 'low'],
[2025, 'high'],
[2095, 'high'],
[2322, 'low'],
[2325, 'low']],
'reserved_high': 2},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'deny',
'allow',
'allow',
'allow',
'allow'],
[2, 2]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[8, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [12, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [8, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [9, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1007, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[5, 'low'],
[5, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[249, 'low'],
[476, 'low'],
[620, 'high'],
[621, 'high'],
[646, 'batch'],
[704, 'low'],
[832, 'batch'],
[989, 'batch'],
[1004, 'batch'],
[1140, 'low'],
[1764, 'low'],
[2209, 'high'],
[2225, 'batch'],
[2378, 'batch']],
'reserved_high': 2},
[['allow',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'deny',
'allow',
'allow',
'deny',
'allow',
'allow',
'allow'],
[2, 1]]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
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 |
|---|---|---|---|
| low traffic cannot take reserve | [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]] | [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]] | Passed |
| high traffic blocks low at capacity | [['allow', 'allow', 'allow', 'allow', 'allow', 'allow'], [3, 3]] | [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]] | Failed |
| unknown priority is low | [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]] | [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]] | Passed |
| custom label cannot claim reserve | [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]] | [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]] | Passed |
| window reset clears both | [['allow', 'allow', 'allow', 'allow', 'allow', 'deny'], [1, 1]] | [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]] | Failed |
| mixed within reserve | [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]] | [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]] | Passed |
| random mix | [['allow', 'allow', 'deny', 'deny', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow', 'allow'], [1, 1]] | [['allow', 'allow', 'deny', 'deny', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow', 'allow'], [1, 1]] | Passed |
SHA-256 / 28947052538fb157256b3d439b87056706c69b761d48ce125f992db93625eb3c
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
cap = x['capacity']
res = x['reserved_high']
win = None
low = high = 0
out = []
for t, prio in x['requests']:
w = t // 1000
if w != win:
win, low, high = w, 0, 0
if prio == 'high':
ok = low + high < cap
else:
ok = low + high < cap - res
if ok:
if prio == 'high':
high += 1
else:
low += 1
out.append('allow')
else:
out.append('deny')
return [out, [low, high]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[4, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [8, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [4, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [5, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1003, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[1, 'low'],
[1, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[23, 'low'],
[30, 'batch'],
[460, 'batch'],
[783, 'low'],
[807, 'high'],
[926, 'low'],
[1133, 'low'],
[1169, 'low'],
[1221, 'high'],
[1686, 'low'],
[1702, 'low'],
[1740, 'low'],
[2424, 'low'],
[2472, 'high']],
'reserved_high': 2},
[['allow',
'allow',
'deny',
'deny',
'allow',
'deny',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'allow',
'allow'],
[1, 1]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[5, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [9, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [5, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [6, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1004, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[2, 'low'],
[2, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[284, 'batch'],
[629, 'low'],
[787, 'low'],
[903, 'low'],
[1032, 'batch'],
[1118, 'high'],
[1495, 'low'],
[1855, 'low'],
[1876, 'low'],
[1919, 'batch'],
[2238, 'high'],
[2382, 'batch'],
[2390, 'high'],
[2492, 'high']],
'reserved_high': 2},
[['allow',
'allow',
'deny',
'deny',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'allow',
'allow',
'allow',
'allow'],
[1, 3]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[6, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [10, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [6, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [7, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1005, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[3, 'low'],
[3, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[99, 'low'],
[696, 'low'],
[811, 'batch'],
[837, 'low'],
[912, 'batch'],
[1070, 'low'],
[1174, 'batch'],
[1400, 'batch'],
[1530, 'low'],
[1887, 'high'],
[1994, 'batch'],
[2235, 'low'],
[2286, 'low'],
[2369, 'high']],
'reserved_high': 2},
[['allow',
'allow',
'deny',
'deny',
'deny',
'allow',
'allow',
'deny',
'deny',
'allow',
'deny',
'allow',
'allow',
'allow'],
[2, 1]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[7, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [11, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [7, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [8, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1006, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[4, 'low'],
[4, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[279, 'high'],
[550, 'high'],
[665, 'low'],
[940, 'low'],
[1010, 'batch'],
[1022, 'low'],
[1597, 'low'],
[1623, 'batch'],
[1749, 'low'],
[1850, 'low'],
[2025, 'high'],
[2095, 'high'],
[2322, 'low'],
[2325, 'low']],
'reserved_high': 2},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'deny',
'allow',
'allow',
'allow',
'allow'],
[2, 2]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[8, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [12, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [8, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [9, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1007, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[5, 'low'],
[5, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[249, 'low'],
[476, 'low'],
[620, 'high'],
[621, 'high'],
[646, 'batch'],
[704, 'low'],
[832, 'batch'],
[989, 'batch'],
[1004, 'batch'],
[1140, 'low'],
[1764, 'low'],
[2209, 'high'],
[2225, 'batch'],
[2378, 'batch']],
'reserved_high': 2},
[['allow',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'deny',
'allow',
'allow',
'deny',
'allow',
'allow',
'allow'],
[2, 1]]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
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 |
|---|---|---|---|
| low traffic cannot take reserve | [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]] | [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]] | Passed |
| high traffic blocks low at capacity | [['allow', 'allow', 'allow', 'deny', 'deny', 'deny'], [0, 3]] | [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]] | Failed |
| unknown priority is low | [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]] | [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]] | Passed |
| custom label cannot claim reserve | [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]] | [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]] | Passed |
| window reset clears both | [['allow', 'allow', 'deny', 'allow', 'deny', 'allow'], [0, 2]] | [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]] | Failed |
| mixed within reserve | [['allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow'], [1, 3]] | [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]] | Failed |
| random mix | [['allow', 'allow', 'deny', 'deny', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow', 'allow'], [1, 1]] | [['allow', 'allow', 'deny', 'deny', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow', 'allow'], [1, 1]] | Passed |
SHA-256 / 40aa34f08e618193a1cdb6381f9b64ce3caa2097d29237f53d8ab28894d6f7cb
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
cap = x['capacity']
res = x['reserved_high']
win = None
low = high = 0
out = []
for t, prio in x['requests']:
w = t // 1000
if w != win:
win, low, high = w, 0, 0
if prio == 'high':
ok = low + high < cap
else:
ok = low < cap - res and low + high < cap
if ok:
if prio == 'high':
high += 1
else:
low += 1
out.append('allow')
else:
out.append('deny')
return [out, [low, high]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[4, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [8, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [4, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [5, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1003, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[1, 'low'],
[1, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[23, 'low'],
[30, 'batch'],
[460, 'batch'],
[783, 'low'],
[807, 'high'],
[926, 'low'],
[1133, 'low'],
[1169, 'low'],
[1221, 'high'],
[1686, 'low'],
[1702, 'low'],
[1740, 'low'],
[2424, 'low'],
[2472, 'high']],
'reserved_high': 2},
[['allow',
'allow',
'deny',
'deny',
'allow',
'deny',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'allow',
'allow'],
[1, 1]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[5, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [9, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [5, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [6, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1004, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[2, 'low'],
[2, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[284, 'batch'],
[629, 'low'],
[787, 'low'],
[903, 'low'],
[1032, 'batch'],
[1118, 'high'],
[1495, 'low'],
[1855, 'low'],
[1876, 'low'],
[1919, 'batch'],
[2238, 'high'],
[2382, 'batch'],
[2390, 'high'],
[2492, 'high']],
'reserved_high': 2},
[['allow',
'allow',
'deny',
'deny',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'allow',
'allow',
'allow',
'allow'],
[1, 3]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[6, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [10, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [6, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [7, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1005, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[3, 'low'],
[3, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[99, 'low'],
[696, 'low'],
[811, 'batch'],
[837, 'low'],
[912, 'batch'],
[1070, 'low'],
[1174, 'batch'],
[1400, 'batch'],
[1530, 'low'],
[1887, 'high'],
[1994, 'batch'],
[2235, 'low'],
[2286, 'low'],
[2369, 'high']],
'reserved_high': 2},
[['allow',
'allow',
'deny',
'deny',
'deny',
'allow',
'allow',
'deny',
'deny',
'allow',
'deny',
'allow',
'allow',
'allow'],
[2, 1]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[7, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [11, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [7, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [8, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1006, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[4, 'low'],
[4, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[279, 'high'],
[550, 'high'],
[665, 'low'],
[940, 'low'],
[1010, 'batch'],
[1022, 'low'],
[1597, 'low'],
[1623, 'batch'],
[1749, 'low'],
[1850, 'low'],
[2025, 'high'],
[2095, 'high'],
[2322, 'low'],
[2325, 'low']],
'reserved_high': 2},
[['allow',
'allow',
'allow',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'deny',
'allow',
'allow',
'allow',
'allow'],
[2, 2]]]],
[['low traffic cannot take reserve',
{'capacity': 5,
'requests': [[0, 'low'],
[0, 'low'],
[0, 'low'],
[0, 'low'],
[1, 'high'],
[2, 'high'],
[8, 'high'],
[4, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]]],
['high traffic blocks low at capacity',
{'capacity': 4,
'requests': [[0, 'high'], [0, 'high'], [0, 'high'], [5, 'low'], [6, 'low'], [12, 'low']],
'reserved_high': 1},
[['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]]],
['unknown priority is low',
{'capacity': 3,
'requests': [[0, 'batch'], [1, 'critical'], [2, 'batch'], [8, 'high'], [4, 'critical']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]]],
['custom label cannot claim reserve',
{'capacity': 4,
'requests': [[0, 'batch'], [1, 'batch'], [2, 'critical'], [3, 'high'], [9, 'high']],
'reserved_high': 2},
[['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]]],
['window reset clears both',
{'capacity': 2,
'requests': [[0, 'high'],
[1, 'high'],
[999, 'low'],
[1000, 'high'],
[1001, 'low'],
[1007, 'high']],
'reserved_high': 1},
[['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]]],
['mixed within reserve',
{'capacity': 6,
'requests': [[0, 'high'],
[0, 'low'],
[0, 'high'],
[0, 'low'],
[0, 'low'],
[5, 'low'],
[5, 'high']],
'reserved_high': 3},
[['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]]],
['random mix',
{'capacity': 4,
'requests': [[249, 'low'],
[476, 'low'],
[620, 'high'],
[621, 'high'],
[646, 'batch'],
[704, 'low'],
[832, 'batch'],
[989, 'batch'],
[1004, 'batch'],
[1140, 'low'],
[1764, 'low'],
[2209, 'high'],
[2225, 'batch'],
[2378, 'batch']],
'reserved_high': 2},
[['allow',
'allow',
'allow',
'allow',
'deny',
'deny',
'deny',
'deny',
'allow',
'allow',
'deny',
'allow',
'allow',
'allow'],
[2, 1]]]]]
for label, args, expected in cases[N - 1]:
check(label, solve(args), expected)
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 |
|---|---|---|---|
| low traffic cannot take reserve | [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]] | [['allow', 'allow', 'allow', 'deny', 'allow', 'allow', 'deny', 'deny'], [3, 2]] | Passed |
| high traffic blocks low at capacity | [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]] | [['allow', 'allow', 'allow', 'allow', 'deny', 'deny'], [1, 3]] | Passed |
| unknown priority is low | [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]] | [['allow', 'allow', 'deny', 'allow', 'deny'], [2, 1]] | Passed |
| custom label cannot claim reserve | [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]] | [['allow', 'allow', 'deny', 'allow', 'allow'], [2, 2]] | Passed |
| window reset clears both | [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]] | [['allow', 'allow', 'deny', 'allow', 'allow', 'deny'], [1, 1]] | Passed |
| mixed within reserve | [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]] | [['allow', 'allow', 'allow', 'allow', 'allow', 'deny', 'allow'], [3, 3]] | Passed |
| random mix | [['allow', 'allow', 'deny', 'deny', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow', 'allow'], [1, 1]] | [['allow', 'allow', 'deny', 'deny', 'allow', 'deny', 'allow', 'allow', 'allow', 'deny', 'deny', 'deny', 'allow', 'allow'], [1, 1]] | Passed |
SHA-256 / 92e658a00a05b3fed2ae53992993c753ba5a6f179aa28bf20adc1a9c1da31f76
Verification & scope
A deterministic, bounded teaching model with stipulated constants and pre-hashed or explicitly hashed inputs; it is not a production implementation and makes no claim of conformance to any library or paper beyond the stated contract. 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:48:49.726251+00:00.
Case digest / 90ee82cc582c81a35a31c599a3bb204cffd2b5ad63f990de128742a5c9e29469