FA-73416 / Rate limiter algorithms / Open access
Fixed-window request counter: one counter shared by every key · case 01
One tenant exhausts the quota for everyone.
ROOT CAUSE
All keys share a single counter.
VERIFIED REPAIR
Keep a separate counter per exact key.
Unsuccessful approach: Lowercasing keys merges distinct case-sensitive API keys.
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('*', [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], ['deny', 0, 480], ['deny', 0, 470], ['deny', 0, 459]] | [['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 459]] | Failed |
| 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', 0, 601], ['deny', 0, 472], ['allow', 2, 533], ['allow', 1, 394], ['allow', 0, 209], ['allow', 2, 730], ['allow', 1, 564], ['allow', 0, 406], ['deny', 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 / 43e8d194d4c14a65d81b812927f1f68bdea3bd57e81e6fd8c25c3d0ac61fc36c
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.lower(), [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], ['deny', 0, 480], ['deny', 0, 470], ['deny', 0, 459]] | [['allow', 0, 490], ['allow', 0, 480], ['allow', 0, 470], ['deny', 0, 459]] | Failed |
| 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 / 85bac2bc4dd7335eeb7696c19a3ceb29594499fc9627274997a78de06735c867
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.426361+00:00.
Case digest / 865927005c9bbe4401094ff190e5bb49ebb04365c726dd1309f54f83f6a41604