FA-73426 / Rate limiter algorithms / Open access
Fixed-window request counter: remaining reported before charging · case 01
The last permitted request is advertised as leaving one more.
ROOT CAUSE
Remaining is computed as if the current request had not been counted.
VERIFIED REPAIR
Report limit minus the count after charging.
Unsuccessful approach: Subtracting one more under-reports the remaining quota.
Case contract
Input {limit, window_ms, requests [[t, key]]}. Windows are epoch-aligned: index t div W. Each (case-sensitive) key keeps [window, count]; a request in a later window resets the count, while a late request from an earlier window is charged to the current window. Allow while count < limit and report remaining = limit - count after charging; denials are not counted. reset = ms until the end of the key's current window. Return [[decision, remaining, reset]].
Why this case matters
Fixed windows are the simplest API quota; alignment, reset and key-identity mistakes show up as double bursts, stuck quotas or cross-tenant throttling.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
L = x['limit']
W = x['window_ms']
state = {}
out = []
for t, key in x['requests']:
idx = t // W
st = state.setdefault(key, [idx, 0])
if idx > st[0]:
st[0] = idx
st[1] = 0
reset = (st[0] + 1) * W - t
if st[1] < L:
st[1] += 1
out.append(['allow', L - st[1] + 1, reset])
else:
out.append(['deny', 0, reset])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1501, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 499]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3101, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 899], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [901, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1099], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [41, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 459]]],
['first request mid window',
{'limit': 2,
'requests': [[701, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 299], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[148, 'p'],
[1350, 'p'],
[1394, 'p'],
[1399, 'q'],
[1528, 'p'],
[2467, 'q'],
[2606, 'p'],
[2791, 'q'],
[3270, 'q'],
[3436, 'p'],
[3594, 'p'],
[3878, 'p']],
'window_ms': 1000},
[['allow', 2, 852],
['allow', 2, 650],
['allow', 1, 606],
['allow', 2, 601],
['allow', 0, 472],
['allow', 2, 533],
['allow', 2, 394],
['allow', 1, 209],
['allow', 2, 730],
['allow', 2, 564],
['allow', 1, 406],
['allow', 0, 122]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1502, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 498]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3102, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 898], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [902, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1098], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [42, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 458]]],
['first request mid window',
{'limit': 2,
'requests': [[702, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 298], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[18, 'q'],
[35, 'q'],
[153, 'p'],
[1576, 'p'],
[1806, 'p'],
[1845, 'q'],
[1907, 'q'],
[2159, 'q'],
[2302, 'p'],
[2922, 'q'],
[3458, 'q'],
[3820, 'q']],
'window_ms': 1000},
[['allow', 2, 982],
['allow', 1, 965],
['allow', 2, 847],
['allow', 2, 424],
['allow', 1, 194],
['allow', 2, 155],
['allow', 1, 93],
['allow', 2, 841],
['allow', 2, 698],
['allow', 1, 78],
['allow', 2, 542],
['allow', 1, 180]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1503, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 497]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3103, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 897], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [903, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1097], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [43, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 457]]],
['first request mid window',
{'limit': 2,
'requests': [[703, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 297], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[39, 'q'],
[40, 'q'],
[204, 'p'],
[348, 'p'],
[694, 'p'],
[1639, 'q'],
[1928, 'p'],
[2192, 'q'],
[2354, 'q'],
[2607, 'p'],
[2877, 'p'],
[3047, 'q']],
'window_ms': 1000},
[['allow', 2, 961],
['allow', 1, 960],
['allow', 2, 796],
['allow', 1, 652],
['allow', 0, 306],
['allow', 2, 361],
['allow', 2, 72],
['allow', 2, 808],
['allow', 1, 646],
['allow', 2, 393],
['allow', 1, 123],
['allow', 2, 953]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1504, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 496]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3104, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 896], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [904, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1096], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [44, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 456]]],
['first request mid window',
{'limit': 2,
'requests': [[704, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 296], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[413, 'p'],
[553, 'q'],
[896, 'p'],
[1203, 'p'],
[1938, 'p'],
[2137, 'q'],
[2305, 'p'],
[2811, 'q'],
[2904, 'p'],
[3215, 'q'],
[3333, 'p'],
[3669, 'q']],
'window_ms': 1000},
[['allow', 2, 587],
['allow', 2, 447],
['allow', 1, 104],
['allow', 2, 797],
['allow', 1, 62],
['allow', 2, 863],
['allow', 2, 695],
['allow', 1, 189],
['allow', 1, 96],
['allow', 2, 785],
['allow', 2, 667],
['allow', 1, 331]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1505, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 495]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3105, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 895], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [905, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1095], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [45, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 455]]],
['first request mid window',
{'limit': 2,
'requests': [[705, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 295], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[265, 'q'],
[437, 'q'],
[695, 'q'],
[1325, 'p'],
[2036, 'p'],
[2449, 'q'],
[2816, 'q'],
[2985, 'q'],
[3033, 'q'],
[3343, 'p'],
[3427, 'q'],
[3729, 'p']],
'window_ms': 1000},
[['allow', 2, 735],
['allow', 1, 563],
['allow', 0, 305],
['allow', 2, 675],
['allow', 2, 964],
['allow', 2, 551],
['allow', 1, 184],
['allow', 0, 15],
['allow', 2, 967],
['allow', 2, 657],
['allow', 1, 573],
['allow', 1, 271]]]]]
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 |
|---|---|---|---|
| window boundary resets | [['allow', 2, 10], ['allow', 1, 5], ['deny', 0, 1], ['allow', 2, 1000], ['allow', 1, 499]] | [['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 499]] | Failed |
| skipped windows reset | [['allow', 2, 900], ['allow', 1, 800], ['allow', 2, 899], ['allow', 1, 800]] | [['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 899], ['allow', 0, 800]] | Failed |
| late request stays in window | [['allow', 3, 900], ['allow', 2, 800], ['allow', 1, 1099], ['deny', 0, 700], ['deny', 0, 600]] | [['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1099], ['deny', 0, 700], ['deny', 0, 600]] | Failed |
| keys are isolated and case-sensitive | [['allow', 1, 490], ['allow', 1, 480], ['allow', 1, 470], ['deny', 0, 459]] | [['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 459]] | Failed |
| first request mid window | [['allow', 2, 299], ['allow', 1, 200], ['allow', 2, 900], ['allow', 1, 800], ['deny', 0, 700]] | [['allow', 1, 299], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]] | Failed |
| random keys | [['allow', 3, 852], ['allow', 3, 650], ['allow', 2, 606], ['allow', 3, 601], ['allow', 1, 472], ['allow', 3, 533], ['allow', 3, 394], ['allow', 2, 209], ['allow', 3, 730], ['allow', 3, 564], ['allow', 2, 406], ['allow', 1, 122]] | [['allow', 2, 852], ['allow', 2, 650], ['allow', 1, 606], ['allow', 2, 601], ['allow', 0, 472], ['allow', 2, 533], ['allow', 2, 394], ['allow', 1, 209], ['allow', 2, 730], ['allow', 2, 564], ['allow', 1, 406], ['allow', 0, 122]] | Failed |
SHA-256 / 5656210c286a23a279a65586ea5b80e6779b3fcdc8857f6e83db06593ca89945
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
L = x['limit']
W = x['window_ms']
state = {}
out = []
for t, key in x['requests']:
idx = t // W
st = state.setdefault(key, [idx, 0])
if idx > st[0]:
st[0] = idx
st[1] = 0
reset = (st[0] + 1) * W - t
if st[1] < L:
st[1] += 1
out.append(['allow', max(0, L - st[1] - 1), reset])
else:
out.append(['deny', 0, reset])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1501, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 499]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3101, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 899], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [901, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1099], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [41, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 459]]],
['first request mid window',
{'limit': 2,
'requests': [[701, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 299], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[148, 'p'],
[1350, 'p'],
[1394, 'p'],
[1399, 'q'],
[1528, 'p'],
[2467, 'q'],
[2606, 'p'],
[2791, 'q'],
[3270, 'q'],
[3436, 'p'],
[3594, 'p'],
[3878, 'p']],
'window_ms': 1000},
[['allow', 2, 852],
['allow', 2, 650],
['allow', 1, 606],
['allow', 2, 601],
['allow', 0, 472],
['allow', 2, 533],
['allow', 2, 394],
['allow', 1, 209],
['allow', 2, 730],
['allow', 2, 564],
['allow', 1, 406],
['allow', 0, 122]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1502, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 498]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3102, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 898], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [902, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1098], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [42, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 458]]],
['first request mid window',
{'limit': 2,
'requests': [[702, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 298], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[18, 'q'],
[35, 'q'],
[153, 'p'],
[1576, 'p'],
[1806, 'p'],
[1845, 'q'],
[1907, 'q'],
[2159, 'q'],
[2302, 'p'],
[2922, 'q'],
[3458, 'q'],
[3820, 'q']],
'window_ms': 1000},
[['allow', 2, 982],
['allow', 1, 965],
['allow', 2, 847],
['allow', 2, 424],
['allow', 1, 194],
['allow', 2, 155],
['allow', 1, 93],
['allow', 2, 841],
['allow', 2, 698],
['allow', 1, 78],
['allow', 2, 542],
['allow', 1, 180]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1503, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 497]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3103, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 897], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [903, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1097], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [43, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 457]]],
['first request mid window',
{'limit': 2,
'requests': [[703, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 297], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[39, 'q'],
[40, 'q'],
[204, 'p'],
[348, 'p'],
[694, 'p'],
[1639, 'q'],
[1928, 'p'],
[2192, 'q'],
[2354, 'q'],
[2607, 'p'],
[2877, 'p'],
[3047, 'q']],
'window_ms': 1000},
[['allow', 2, 961],
['allow', 1, 960],
['allow', 2, 796],
['allow', 1, 652],
['allow', 0, 306],
['allow', 2, 361],
['allow', 2, 72],
['allow', 2, 808],
['allow', 1, 646],
['allow', 2, 393],
['allow', 1, 123],
['allow', 2, 953]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1504, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 496]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3104, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 896], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [904, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1096], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [44, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 456]]],
['first request mid window',
{'limit': 2,
'requests': [[704, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 296], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[413, 'p'],
[553, 'q'],
[896, 'p'],
[1203, 'p'],
[1938, 'p'],
[2137, 'q'],
[2305, 'p'],
[2811, 'q'],
[2904, 'p'],
[3215, 'q'],
[3333, 'p'],
[3669, 'q']],
'window_ms': 1000},
[['allow', 2, 587],
['allow', 2, 447],
['allow', 1, 104],
['allow', 2, 797],
['allow', 1, 62],
['allow', 2, 863],
['allow', 2, 695],
['allow', 1, 189],
['allow', 1, 96],
['allow', 2, 785],
['allow', 2, 667],
['allow', 1, 331]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1505, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 495]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3105, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 895], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [905, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1095], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [45, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 455]]],
['first request mid window',
{'limit': 2,
'requests': [[705, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 295], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[265, 'q'],
[437, 'q'],
[695, 'q'],
[1325, 'p'],
[2036, 'p'],
[2449, 'q'],
[2816, 'q'],
[2985, 'q'],
[3033, 'q'],
[3343, 'p'],
[3427, 'q'],
[3729, 'p']],
'window_ms': 1000},
[['allow', 2, 735],
['allow', 1, 563],
['allow', 0, 305],
['allow', 2, 675],
['allow', 2, 964],
['allow', 2, 551],
['allow', 1, 184],
['allow', 0, 15],
['allow', 2, 967],
['allow', 2, 657],
['allow', 1, 573],
['allow', 1, 271]]]]]
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 |
|---|---|---|---|
| window boundary resets | [['allow', 0, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 0, 1000], ['allow', 0, 499]] | [['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 499]] | Failed |
| skipped windows reset | [['allow', 0, 900], ['allow', 0, 800], ['allow', 0, 899], ['allow', 0, 800]] | [['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 899], ['allow', 0, 800]] | Failed |
| late request stays in window | [['allow', 1, 900], ['allow', 0, 800], ['allow', 0, 1099], ['deny', 0, 700], ['deny', 0, 600]] | [['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1099], ['deny', 0, 700], ['deny', 0, 600]] | Failed |
| keys are isolated and case-sensitive | [['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 459]] | [['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 459]] | Passed |
| first request mid window | [['allow', 0, 299], ['allow', 0, 200], ['allow', 0, 900], ['allow', 0, 800], ['deny', 0, 700]] | [['allow', 1, 299], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]] | Failed |
| random keys | [['allow', 1, 852], ['allow', 1, 650], ['allow', 0, 606], ['allow', 1, 601], ['allow', 0, 472], ['allow', 1, 533], ['allow', 1, 394], ['allow', 0, 209], ['allow', 1, 730], ['allow', 1, 564], ['allow', 0, 406], ['allow', 0, 122]] | [['allow', 2, 852], ['allow', 2, 650], ['allow', 1, 606], ['allow', 2, 601], ['allow', 0, 472], ['allow', 2, 533], ['allow', 2, 394], ['allow', 1, 209], ['allow', 2, 730], ['allow', 2, 564], ['allow', 1, 406], ['allow', 0, 122]] | Failed |
SHA-256 / b2baf2129f3fd3e66c8e211c4118ad7b9ef2e5368585f4ec093d107fcdb958ec
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
L = x['limit']
W = x['window_ms']
state = {}
out = []
for t, key in x['requests']:
idx = t // W
st = state.setdefault(key, [idx, 0])
if idx > st[0]:
st[0] = idx
st[1] = 0
reset = (st[0] + 1) * W - t
if st[1] < L:
st[1] += 1
out.append(['allow', L - st[1], reset])
else:
out.append(['deny', 0, reset])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1501, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 499]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3101, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 899], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [901, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1099], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [41, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 459]]],
['first request mid window',
{'limit': 2,
'requests': [[701, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 299], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[148, 'p'],
[1350, 'p'],
[1394, 'p'],
[1399, 'q'],
[1528, 'p'],
[2467, 'q'],
[2606, 'p'],
[2791, 'q'],
[3270, 'q'],
[3436, 'p'],
[3594, 'p'],
[3878, 'p']],
'window_ms': 1000},
[['allow', 2, 852],
['allow', 2, 650],
['allow', 1, 606],
['allow', 2, 601],
['allow', 0, 472],
['allow', 2, 533],
['allow', 2, 394],
['allow', 1, 209],
['allow', 2, 730],
['allow', 2, 564],
['allow', 1, 406],
['allow', 0, 122]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1502, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 498]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3102, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 898], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [902, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1098], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [42, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 458]]],
['first request mid window',
{'limit': 2,
'requests': [[702, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 298], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[18, 'q'],
[35, 'q'],
[153, 'p'],
[1576, 'p'],
[1806, 'p'],
[1845, 'q'],
[1907, 'q'],
[2159, 'q'],
[2302, 'p'],
[2922, 'q'],
[3458, 'q'],
[3820, 'q']],
'window_ms': 1000},
[['allow', 2, 982],
['allow', 1, 965],
['allow', 2, 847],
['allow', 2, 424],
['allow', 1, 194],
['allow', 2, 155],
['allow', 1, 93],
['allow', 2, 841],
['allow', 2, 698],
['allow', 1, 78],
['allow', 2, 542],
['allow', 1, 180]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1503, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 497]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3103, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 897], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [903, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1097], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [43, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 457]]],
['first request mid window',
{'limit': 2,
'requests': [[703, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 297], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[39, 'q'],
[40, 'q'],
[204, 'p'],
[348, 'p'],
[694, 'p'],
[1639, 'q'],
[1928, 'p'],
[2192, 'q'],
[2354, 'q'],
[2607, 'p'],
[2877, 'p'],
[3047, 'q']],
'window_ms': 1000},
[['allow', 2, 961],
['allow', 1, 960],
['allow', 2, 796],
['allow', 1, 652],
['allow', 0, 306],
['allow', 2, 361],
['allow', 2, 72],
['allow', 2, 808],
['allow', 1, 646],
['allow', 2, 393],
['allow', 1, 123],
['allow', 2, 953]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1504, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 496]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3104, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 896], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [904, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1096], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [44, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 456]]],
['first request mid window',
{'limit': 2,
'requests': [[704, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 296], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[413, 'p'],
[553, 'q'],
[896, 'p'],
[1203, 'p'],
[1938, 'p'],
[2137, 'q'],
[2305, 'p'],
[2811, 'q'],
[2904, 'p'],
[3215, 'q'],
[3333, 'p'],
[3669, 'q']],
'window_ms': 1000},
[['allow', 2, 587],
['allow', 2, 447],
['allow', 1, 104],
['allow', 2, 797],
['allow', 1, 62],
['allow', 2, 863],
['allow', 2, 695],
['allow', 1, 189],
['allow', 1, 96],
['allow', 2, 785],
['allow', 2, 667],
['allow', 1, 331]]]],
[['window boundary resets',
{'limit': 2,
'requests': [[990, 'k'], [995, 'k'], [999, 'k'], [1000, 'k'], [1505, 'k']],
'window_ms': 1000},
[['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 495]]],
['skipped windows reset',
{'limit': 2, 'requests': [[100, 'a'], [200, 'a'], [3105, 'a'], [3200, 'a']], 'window_ms': 1000},
[['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 895], ['allow', 0, 800]]],
['late request stays in window',
{'limit': 3,
'requests': [[1100, 'a'], [1200, 'a'], [905, 'a'], [1300, 'a'], [1400, 'a']],
'window_ms': 1000},
[['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1095], ['deny', 0, 700], ['deny', 0, 600]]],
['keys are isolated and case-sensitive',
{'limit': 1, 'requests': [[10, 'Key'], [20, 'key'], [30, 'KEY'], [45, 'Key']], 'window_ms': 500},
[['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 455]]],
['first request mid window',
{'limit': 2,
'requests': [[705, 'z'], [800, 'z'], [1100, 'z'], [1200, 'z'], [1300, 'z']],
'window_ms': 1000},
[['allow', 1, 295], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]]],
['random keys',
{'limit': 3,
'requests': [[265, 'q'],
[437, 'q'],
[695, 'q'],
[1325, 'p'],
[2036, 'p'],
[2449, 'q'],
[2816, 'q'],
[2985, 'q'],
[3033, 'q'],
[3343, 'p'],
[3427, 'q'],
[3729, 'p']],
'window_ms': 1000},
[['allow', 2, 735],
['allow', 1, 563],
['allow', 0, 305],
['allow', 2, 675],
['allow', 2, 964],
['allow', 2, 551],
['allow', 1, 184],
['allow', 0, 15],
['allow', 2, 967],
['allow', 2, 657],
['allow', 1, 573],
['allow', 1, 271]]]]]
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 |
|---|---|---|---|
| window boundary resets | [['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 499]] | [['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 499]] | Passed |
| skipped windows reset | [['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 899], ['allow', 0, 800]] | [['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 899], ['allow', 0, 800]] | Passed |
| late request stays in window | [['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1099], ['deny', 0, 700], ['deny', 0, 600]] | [['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1099], ['deny', 0, 700], ['deny', 0, 600]] | Passed |
| keys are isolated and case-sensitive | [['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 459]] | [['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 459]] | Passed |
| first request mid window | [['allow', 1, 299], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]] | [['allow', 1, 299], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]] | Passed |
| random keys | [['allow', 2, 852], ['allow', 2, 650], ['allow', 1, 606], ['allow', 2, 601], ['allow', 0, 472], ['allow', 2, 533], ['allow', 2, 394], ['allow', 1, 209], ['allow', 2, 730], ['allow', 2, 564], ['allow', 1, 406], ['allow', 0, 122]] | [['allow', 2, 852], ['allow', 2, 650], ['allow', 1, 606], ['allow', 2, 601], ['allow', 0, 472], ['allow', 2, 533], ['allow', 2, 394], ['allow', 1, 209], ['allow', 2, 730], ['allow', 2, 564], ['allow', 1, 406], ['allow', 0, 122]] | Passed |
SHA-256 / 858fe147fad65170706de48a9d3a66221d5b67ff069427663b0eaaa7ce59aaa3
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:47.514234+00:00.
Case digest / 56c7c6064bac7748f7a3c6a0b726e1da3d0ac9cc6dce4edb990877d724f1b15a