FA-73441 / Rate limiter algorithms / Open access
Sliding-window log limiter: denied requests extend the lockout · case 01
A client that keeps retrying never recovers because every denial is logged.
ROOT CAUSE
Denied requests are appended to the log.
VERIFIED REPAIR
Log only admitted requests.
Unsuccessful approach: Trimming the log to the newest L entries still records denials and discards older admitted ones.
Case contract
Input {limit, window_ms, requests [t]}. The limiter clock is now = max of all timestamps seen, so a late request is evaluated at now. Log entries with s <= now - W are pruned. Allow while fewer than limit entries remain and log now; denials are not logged and report retry = oldest + W - now. Return [[decision, retry]], final log].
Why this case matters
Sliding logs give exact rolling-window limits for login attempts and expensive endpoints; pruning and logging rules decide exactly when a client may retry.
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']
log = []
now = None
out = []
for t in x['requests']:
now = t if now is None else max(now, t)
log = [s for s in log if s > now - W]
if len(log) < L:
log.append(now)
out.append(['allow', 0])
else:
log.append(now)
out.append(['deny', log[0] + W - now])
return [out, log]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1011, 1012], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1051, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1051, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 101, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 701, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 299],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [737, 924, 1194, 1231, 1362, 1408, 1509, 1520, 1559, 1643, 1776, 2570],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 306],
['deny', 175],
['deny', 129],
['deny', 28],
['deny', 17],
['allow', 0],
['deny', 81],
['allow', 0],
['allow', 0]],
[1776, 2570]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 151, 251], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1012, 1013], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 987]], [1000, 1012]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1052, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1052, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 102, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 702, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 298],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [203, 368, 954, 964, 1092, 1537, 1711, 1845, 1983, 2392, 2599, 2816],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 39],
['allow', 0],
['allow', 0],
['deny', 43],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 46],
['allow', 0]],
[2392, 2816]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 152, 252], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 48], ['allow', 0]], [252]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1013, 1014], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 986]], [1000, 1013]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1053, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1053, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 103, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 703, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 297],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [659, 794, 1414, 1446, 1627, 2009, 2196, 2262, 2536, 2557, 2734, 2819],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 13],
['allow', 0],
['allow', 0],
['deny', 18],
['allow', 0],
['allow', 0],
['deny', 252],
['deny', 75],
['allow', 0]],
[2262, 2536, 2819]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 153, 253], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 47], ['allow', 0]], [253]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1014, 1015], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 985]], [1000, 1014]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1054, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1054, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 104, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 704, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 296],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [81, 344, 553, 1450, 1591, 1736, 1934, 2492, 2556, 2664, 2677, 2831],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 316],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 615],
['deny', 461]],
[2492, 2556, 2664]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 154, 254], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 46], ['allow', 0]], [254]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1015, 1016], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 984]], [1000, 1015]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1055, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1055, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 105, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 705, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 295],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [85, 117, 140, 309, 683, 1093, 2036, 2231, 2349, 2416, 2706, 2868],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 576],
['deny', 202],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 420],
['deny', 130],
['allow', 0]],
[2231, 2349, 2868]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 155, 255], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 45], ['allow', 0]], [255]]]]]
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 |
|---|---|---|---|
| exact expiry boundary | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011, 1012]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]] | Failed |
| denied requests not logged | [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['deny', 49], ['deny', 50]], [200, 300, 1051, 1150]] | [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]], [1051, 1150]] | Failed |
| late timestamp uses monotonic now | [[['allow', 0], ['allow', 0], ['deny', 450], ['deny', 50], ['deny', 45], ['deny', 440]], [900, 905, 960]] | [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]], [900, 960]] | Failed |
| retry after oldest expires | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 299], ['deny', 1], ['deny', 300], ['deny', 299]], [300, 600, 701, 999, 1000, 1001]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 299], ['deny', 1], ['allow', 0], ['deny', 299]], [300, 600, 1000]] | Failed |
| random traffic | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 306], ['deny', 175], ['deny', 129], ['deny', 28], ['deny', 17], ['deny', 165], ['deny', 81], ['deny', 218], ['allow', 0]], [1776, 2570]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 306], ['deny', 175], ['deny', 129], ['deny', 28], ['deny', 17], ['allow', 0], ['deny', 81], ['allow', 0], ['allow', 0]], [1776, 2570]] | Failed |
| single slot | [[['allow', 0], ['deny', 50], ['deny', 50], ['deny', 49], ['allow', 0]], [251]] | [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]] | Failed |
SHA-256 / e20ab3cf097aa393314fbcd95409fbfc698fda65ac872b46c456c5bfd91f266f
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']
log = []
now = None
out = []
for t in x['requests']:
now = t if now is None else max(now, t)
log = [s for s in log if s > now - W]
if len(log) < L:
log.append(now)
out.append(['allow', 0])
else:
log.append(now)
log = log[-L:]
out.append(['deny', log[0] + W - now])
return [out, log]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1011, 1012], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1051, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1051, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 101, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 701, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 299],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [737, 924, 1194, 1231, 1362, 1408, 1509, 1520, 1559, 1643, 1776, 2570],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 306],
['deny', 175],
['deny', 129],
['deny', 28],
['deny', 17],
['allow', 0],
['deny', 81],
['allow', 0],
['allow', 0]],
[1776, 2570]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 151, 251], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1012, 1013], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 987]], [1000, 1012]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1052, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1052, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 102, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 702, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 298],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [203, 368, 954, 964, 1092, 1537, 1711, 1845, 1983, 2392, 2599, 2816],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 39],
['allow', 0],
['allow', 0],
['deny', 43],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 46],
['allow', 0]],
[2392, 2816]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 152, 252], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 48], ['allow', 0]], [252]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1013, 1014], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 986]], [1000, 1013]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1053, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1053, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 103, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 703, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 297],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [659, 794, 1414, 1446, 1627, 2009, 2196, 2262, 2536, 2557, 2734, 2819],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 13],
['allow', 0],
['allow', 0],
['deny', 18],
['allow', 0],
['allow', 0],
['deny', 252],
['deny', 75],
['allow', 0]],
[2262, 2536, 2819]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 153, 253], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 47], ['allow', 0]], [253]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1014, 1015], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 985]], [1000, 1014]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1054, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1054, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 104, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 704, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 296],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [81, 344, 553, 1450, 1591, 1736, 1934, 2492, 2556, 2664, 2677, 2831],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 316],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 615],
['deny', 461]],
[2492, 2556, 2664]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 154, 254], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 46], ['allow', 0]], [254]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1015, 1016], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 984]], [1000, 1015]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1055, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1055, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 105, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 705, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 295],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [85, 117, 140, 309, 683, 1093, 2036, 2231, 2349, 2416, 2706, 2868],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 576],
['deny', 202],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 420],
['deny', 130],
['allow', 0]],
[2231, 2349, 2868]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 155, 255], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 45], ['allow', 0]], [255]]]]]
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 |
|---|---|---|---|
| exact expiry boundary | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 999]], [1011, 1012]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]] | Failed |
| denied requests not logged | [[['allow', 0], ['allow', 0], ['deny', 900], ['deny', 900], ['deny', 249], ['deny', 901]], [1051, 1150]] | [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]], [1051, 1150]] | Failed |
| late timestamp uses monotonic now | [[['allow', 0], ['allow', 0], ['deny', 500], ['deny', 50], ['deny', 495], ['deny', 445]], [905, 960]] | [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]], [900, 960]] | Failed |
| retry after oldest expires | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 599], ['deny', 601], ['deny', 701], ['deny', 998]], [999, 1000, 1001]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 299], ['deny', 1], ['allow', 0], ['deny', 299]], [300, 600, 1000]] | Failed |
| random traffic | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 493], ['deny', 632], ['deny', 623], ['deny', 653], ['deny', 688], ['deny', 750], ['deny', 677], ['deny', 583], ['allow', 0]], [1776, 2570]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 306], ['deny', 175], ['deny', 129], ['deny', 28], ['deny', 17], ['allow', 0], ['deny', 81], ['allow', 0], ['allow', 0]], [1776, 2570]] | Failed |
| single slot | [[['allow', 0], ['deny', 100], ['deny', 100], ['deny', 100], ['allow', 0]], [251]] | [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]] | Failed |
SHA-256 / ca81ab114cb084c10c22288f1d8f8e37f9328f31a6bd225a384b5cb46b6b06b1
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']
log = []
now = None
out = []
for t in x['requests']:
now = t if now is None else max(now, t)
log = [s for s in log if s > now - W]
if len(log) < L:
log.append(now)
out.append(['allow', 0])
else:
out.append(['deny', log[0] + W - now])
return [out, log]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1011, 1012], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1051, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1051, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 101, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 701, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 299],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [737, 924, 1194, 1231, 1362, 1408, 1509, 1520, 1559, 1643, 1776, 2570],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 306],
['deny', 175],
['deny', 129],
['deny', 28],
['deny', 17],
['allow', 0],
['deny', 81],
['allow', 0],
['allow', 0]],
[1776, 2570]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 151, 251], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1012, 1013], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 987]], [1000, 1012]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1052, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1052, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 102, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 702, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 298],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [203, 368, 954, 964, 1092, 1537, 1711, 1845, 1983, 2392, 2599, 2816],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 39],
['allow', 0],
['allow', 0],
['deny', 43],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 46],
['allow', 0]],
[2392, 2816]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 152, 252], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 48], ['allow', 0]], [252]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1013, 1014], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 986]], [1000, 1013]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1053, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1053, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 103, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 703, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 297],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [659, 794, 1414, 1446, 1627, 2009, 2196, 2262, 2536, 2557, 2734, 2819],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 13],
['allow', 0],
['allow', 0],
['deny', 18],
['allow', 0],
['allow', 0],
['deny', 252],
['deny', 75],
['allow', 0]],
[2262, 2536, 2819]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 153, 253], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 47], ['allow', 0]], [253]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1014, 1015], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 985]], [1000, 1014]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1054, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1054, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 104, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 704, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 296],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [81, 344, 553, 1450, 1591, 1736, 1934, 2492, 2556, 2664, 2677, 2831],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 316],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 615],
['deny', 461]],
[2492, 2556, 2664]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 154, 254], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 46], ['allow', 0]], [254]]]],
[['exact expiry boundary',
{'limit': 2, 'requests': [0, 10, 1000, 1015, 1016], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 984]], [1000, 1015]]],
['denied requests not logged',
{'limit': 2, 'requests': [0, 100, 200, 300, 1055, 1150], 'window_ms': 1000},
[[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]],
[1055, 1150]]],
['late timestamp uses monotonic now',
{'limit': 2, 'requests': [400, 450, 105, 900, 905, 960], 'window_ms': 500},
[[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]],
[900, 960]]],
['retry after oldest expires',
{'limit': 3, 'requests': [0, 300, 600, 705, 999, 1000, 1001], 'window_ms': 1000},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 295],
['deny', 1],
['allow', 0],
['deny', 299]],
[300, 600, 1000]]],
['random traffic',
{'limit': 3,
'requests': [85, 117, 140, 309, 683, 1093, 2036, 2231, 2349, 2416, 2706, 2868],
'window_ms': 800},
[[['allow', 0],
['allow', 0],
['allow', 0],
['deny', 576],
['deny', 202],
['allow', 0],
['allow', 0],
['allow', 0],
['allow', 0],
['deny', 420],
['deny', 130],
['allow', 0]],
[2231, 2349, 2868]]],
['single slot',
{'limit': 1, 'requests': [0, 50, 100, 155, 255], 'window_ms': 100},
[[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 45], ['allow', 0]], [255]]]]]
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 |
|---|---|---|---|
| exact expiry boundary | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['allow', 0], ['deny', 988]], [1000, 1011]] | Passed |
| denied requests not logged | [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]], [1051, 1150]] | [[['allow', 0], ['allow', 0], ['deny', 800], ['deny', 700], ['allow', 0], ['allow', 0]], [1051, 1150]] | Passed |
| late timestamp uses monotonic now | [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]], [900, 960]] | [[['allow', 0], ['allow', 0], ['deny', 450], ['allow', 0], ['deny', 45], ['allow', 0]], [900, 960]] | Passed |
| retry after oldest expires | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 299], ['deny', 1], ['allow', 0], ['deny', 299]], [300, 600, 1000]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 299], ['deny', 1], ['allow', 0], ['deny', 299]], [300, 600, 1000]] | Passed |
| random traffic | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 306], ['deny', 175], ['deny', 129], ['deny', 28], ['deny', 17], ['allow', 0], ['deny', 81], ['allow', 0], ['allow', 0]], [1776, 2570]] | [[['allow', 0], ['allow', 0], ['allow', 0], ['deny', 306], ['deny', 175], ['deny', 129], ['deny', 28], ['deny', 17], ['allow', 0], ['deny', 81], ['allow', 0], ['allow', 0]], [1776, 2570]] | Passed |
| single slot | [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]] | [[['allow', 0], ['deny', 50], ['allow', 0], ['deny', 49], ['allow', 0]], [251]] | Passed |
SHA-256 / ffe51265a277ce4d7596f91f3be68a941ede7195d2ea2fe528e7085fe3934f40
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.554716+00:00.
Case digest / 989c0574666c4475112e4abd9656f13127da96e207532e221cf33e96512395ca