FA-73421 / Rate limiter algorithms / Open access
Fixed-window request counter: reset reported as an absolute time · case 01
Clients interpret an epoch timestamp as a delay and back off for decades.
ROOT CAUSE
The reset value is the absolute end of the window instead of the time remaining.
VERIFIED REPAIR
Report the milliseconds until the current window ends.
Unsuccessful approach: Using the late request's own window reports a reset in the past.
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
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, 1000], ['allow', 0, 1000], ['deny', 0, 1000], ['allow', 1, 2000], ['allow', 0, 2000]] | [['allow', 1, 10], ['allow', 0, 5], ['deny', 0, 1], ['allow', 1, 1000], ['allow', 0, 499]] | Failed |
| skipped windows reset | [['allow', 1, 1000], ['allow', 0, 1000], ['allow', 1, 4000], ['allow', 0, 4000]] | [['allow', 1, 900], ['allow', 0, 800], ['allow', 1, 899], ['allow', 0, 800]] | Failed |
| late request stays in window | [['allow', 2, 2000], ['allow', 1, 2000], ['allow', 0, 2000], ['deny', 0, 2000], ['deny', 0, 2000]] | [['allow', 2, 900], ['allow', 1, 800], ['allow', 0, 1099], ['deny', 0, 700], ['deny', 0, 600]] | Failed |
| keys are isolated and case-sensitive | [['allow', 0, 500], ['allow', 0, 500], ['allow', 0, 500], ['deny', 0, 500]] | [['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 459]] | Failed |
| first request mid window | [['allow', 1, 1000], ['allow', 0, 1000], ['allow', 1, 2000], ['allow', 0, 2000], ['deny', 0, 2000]] | [['allow', 1, 299], ['allow', 0, 200], ['allow', 1, 900], ['allow', 0, 800], ['deny', 0, 700]] | Failed |
| random keys | [['allow', 2, 1000], ['allow', 2, 2000], ['allow', 1, 2000], ['allow', 2, 2000], ['allow', 0, 2000], ['allow', 2, 3000], ['allow', 2, 3000], ['allow', 1, 3000], ['allow', 2, 4000], ['allow', 2, 4000], ['allow', 1, 4000], ['allow', 0, 4000]] | [['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 / d0561f2217fb8440c37a02bc6d76b4bf0117b73972b2db5d649345c9f003bb31
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 = (idx + 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, 99], ['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', 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 / dff4c2f00a07dfaf8f2f3a8d0203150c3d4fa35880ffade04c4c6b1dd7565ce5
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.502095+00:00.
Case digest / 1dec97cb967af756cf51c8152cef7bb48d1a5f0074870a866c6b4e7f50b18af3