FA-73451 / Rate limiter algorithms / Open access
Sliding-window log limiter: late timestamp rewinds the limiter clock · case 01
A delayed request is evaluated in the past and resurrects expired entries.
ROOT CAUSE
The limiter clock is set to each request timestamp, even when it moves backwards.
VERIFIED REPAIR
Use the maximum timestamp seen as the limiter clock.
Unsuccessful approach: Advancing the clock by one millisecond for late requests invents time that never passed.
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
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', 799], ['allow', 0], ['deny', 45], ['allow', 0]], [900, 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], ['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 / 59877a0ec9f5c8389bfe11d2ec6455b5032791fea3c3a10837f81d2acdf905af
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 or t >= now else now + 1
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', 449], ['allow', 0], ['deny', 45], ['allow', 0]], [900, 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], ['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 / e869166539e15bf601fe05efecad01b55979e6cfb23f28a710a352c43160cb7b
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.674300+00:00.
Case digest / a278feb29c00338289a859f9cad277f341f5ee67b9fcce9c472fef8324693f1e