FA-73411 / Rate limiter algorithms / Open access
Fixed-window request counter: reset only for the immediately next window · case 01
A key idle for more than one window keeps its exhausted count forever.
ROOT CAUSE
The counter resets only when the new window is exactly one after the stored window.
VERIFIED REPAIR
Reset whenever the request falls in a later window.
Unsuccessful approach: Resetting on any different window lets a late request from an earlier window wipe the current count.
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] + 1:
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], ['deny', 0, -2101], ['deny', 0, -2200]] | [['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 899], ['allow', 0, 800]] | Failed |
| 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 / fadcdeefd7de51a70eee31497682d25a388a92f8c4898a000deac317b15ee314
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', 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', 2, 99], ['allow', 2, 700], ['allow', 1, 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', 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 / 19a4b83ef0317cf27072a06857e773e43652f8cedb7a2c8b8c5932b8c850e038
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.368206+00:00.
Case digest / 05bf35587cc1744f1ffaada025a05b12592eef4988729225c0d86bd22a11d986