FA-73781 / Rate limiter algorithms / Open access
EWMA arrival-rate throttle: late arrival rewinds the clock · case 01
After a late arrival the next interval is measured from the past and appears artificially long or short.
ROOT CAUSE
The last-arrival time is overwritten with each timestamp.
VERIFIED REPAIR
Keep the latest arrival time seen.
Unsuccessful approach: Nudging the clock forward by one millisecond on late arrivals invents time.
Case contract
Input {tau_ms, limit_rps, requests [t_ms]}. The rate estimate r starts at 0. For each arrival strictly after the latest seen time, dt = t - last, a = exp(-dt/tau) and r = a*r + (1-a)*(1000/dt) requests per second. Simultaneous or late arrivals leave r unchanged and never move the clock backwards. Every arrival reports deny if r > limit else allow, with r rounded to 3 decimals.
Why this case matters
Irregular-interval EWMA estimators throttle clients by smoothed request rate; time-unit and duplicate-timestamp handling decide whether bursts are detected.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
tau = x['tau_ms']
lim = x['limit_rps']
r = 0.0
last = None
out = []
for t in x['requests']:
if last is not None and t > last:
dt = t - last
a = math.exp(-dt / tau)
r = a * r + (1 - a) * (1000.0 / dt)
last = t
out.append(['deny' if r > lim else 'allow', round(r, 3)])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['steady ten per second',
{'limit_rps': 12, 'requests': [1, 101, 201, 301, 401, 501, 601, 701, 801, 901], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 51, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.499],
['allow', 2.319]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 401, 401], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.966],
['allow', 1.966]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 301, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [714, 757, 953, 1023, 1049, 1069, 1190, 1379, 2031, 2512, 2526, 2977],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.386],
['allow', 2.293],
['allow', 3.434],
['allow', 4.712],
['allow', 5.987],
['deny', 6.349],
['deny', 6.098],
['allow', 3.332],
['allow', 2.709],
['allow', 4.07],
['allow', 3.19]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6001, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [2, 102, 202, 302, 402, 502, 602, 702, 802, 902], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 52, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.482],
['allow', 2.32]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 402, 402], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.964],
['allow', 1.964]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 302, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [216, 250, 522, 784, 966, 1254, 1553, 2058, 2080, 2239, 2561, 2685],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.394],
['allow', 2.129],
['allow', 2.656],
['allow', 3.306],
['allow', 3.362],
['allow', 3.356],
['allow', 2.649],
['allow', 3.973],
['allow', 4.444],
['allow', 3.95],
['allow', 4.618]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6002, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [3, 103, 203, 303, 403, 503, 603, 703, 803, 903], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 53, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.465],
['allow', 2.321]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 403, 403], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.962],
['allow', 1.962]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 303, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [86, 138, 254, 788, 1018, 1187, 1336, 1765, 2119, 2249, 2554, 2910],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.377],
['allow', 2.483],
['allow', 2.157],
['allow', 2.771],
['allow', 3.446],
['allow', 4.072],
['allow', 3.274],
['allow', 3.096],
['allow', 3.875],
['allow', 3.664],
['allow', 3.323]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6003, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [4, 104, 204, 304, 404, 504, 604, 704, 804, 904], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 54, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.448],
['allow', 2.322]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 404, 404], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.96],
['allow', 1.96]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 304, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [385, 507, 716, 724, 1100, 1757, 1778, 1945, 2017, 2160, 2509, 2770],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.311],
['allow', 2.208],
['allow', 3.603],
['allow', 3.211],
['allow', 2.183],
['allow', 3.526],
['allow', 4.048],
['allow', 5.01],
['allow', 5.376],
['allow', 4.391],
['allow', 4.217]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6004, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [5, 105, 205, 305, 405, 505, 605, 705, 805, 905], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 55, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.431],
['allow', 2.323]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 405, 405], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.959],
['allow', 1.959]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 305, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [165, 419, 489, 1134, 1196, 1250, 1558, 1747, 2333, 2495, 2720, 2742],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.198],
['allow', 2.444],
['allow', 1.906],
['allow', 3.111],
['allow', 4.255],
['allow', 3.896],
['allow', 4.226],
['allow', 2.797],
['allow', 3.495],
['allow', 3.756],
['allow', 5.046]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6005, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]]]
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 |
|---|---|---|---|
| steady ten per second | [['allow', 0.0], ['allow', 0.952], ['allow', 1.813], ['allow', 2.592], ['allow', 3.297], ['allow', 3.935], ['allow', 4.512], ['allow', 5.034], ['allow', 5.507], ['allow', 5.934]] | [['allow', 0.0], ['allow', 0.952], ['allow', 1.813], ['allow', 2.592], ['allow', 3.297], ['allow', 3.935], ['allow', 4.512], ['allow', 5.034], ['allow', 5.507], ['allow', 5.934]] | Passed |
| burst crosses limit | [['allow', 0.0], ['allow', 1.98], ['allow', 3.921], ['allow', 5.824], ['allow', 7.688], ['allow', 9.499], ['allow', 2.319]] | [['allow', 0.0], ['allow', 1.98], ['allow', 3.921], ['allow', 5.824], ['allow', 7.688], ['allow', 9.499], ['allow', 2.319]] | Passed |
| simultaneous arrivals | [['allow', 0.0], ['allow', 1.106], ['allow', 1.106], ['allow', 1.106], ['allow', 1.966], ['allow', 1.966]] | [['allow', 0.0], ['allow', 1.106], ['allow', 1.106], ['allow', 1.106], ['allow', 1.966], ['allow', 1.966]] | Passed |
| late arrival ignored for clock | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.353], ['allow', 2.014]] | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]] | Failed |
| random arrivals | [['allow', 0.0], ['allow', 1.386], ['allow', 2.293], ['allow', 3.434], ['allow', 4.712], ['allow', 5.987], ['deny', 6.349], ['deny', 6.098], ['allow', 3.332], ['allow', 2.709], ['allow', 4.07], ['allow', 3.19]] | [['allow', 0.0], ['allow', 1.386], ['allow', 2.293], ['allow', 3.434], ['allow', 4.712], ['allow', 5.987], ['deny', 6.349], ['deny', 6.098], ['allow', 3.332], ['allow', 2.709], ['allow', 4.07], ['allow', 3.19]] | Passed |
| slow client | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | Passed |
SHA-256 / 42ac7fa29de6b19cc33a35ed1f2489f72f69509cec2b7863af1bdad79548a56f
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
tau = x['tau_ms']
lim = x['limit_rps']
r = 0.0
last = None
out = []
for t in x['requests']:
if last is not None and t > last:
dt = t - last
a = math.exp(-dt / tau)
r = a * r + (1 - a) * (1000.0 / dt)
last = t if last is None or t > last else last + 1
out.append(['deny' if r > lim else 'allow', round(r, 3)])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['steady ten per second',
{'limit_rps': 12, 'requests': [1, 101, 201, 301, 401, 501, 601, 701, 801, 901], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 51, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.499],
['allow', 2.319]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 401, 401], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.966],
['allow', 1.966]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 301, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [714, 757, 953, 1023, 1049, 1069, 1190, 1379, 2031, 2512, 2526, 2977],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.386],
['allow', 2.293],
['allow', 3.434],
['allow', 4.712],
['allow', 5.987],
['deny', 6.349],
['deny', 6.098],
['allow', 3.332],
['allow', 2.709],
['allow', 4.07],
['allow', 3.19]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6001, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [2, 102, 202, 302, 402, 502, 602, 702, 802, 902], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 52, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.482],
['allow', 2.32]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 402, 402], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.964],
['allow', 1.964]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 302, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [216, 250, 522, 784, 966, 1254, 1553, 2058, 2080, 2239, 2561, 2685],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.394],
['allow', 2.129],
['allow', 2.656],
['allow', 3.306],
['allow', 3.362],
['allow', 3.356],
['allow', 2.649],
['allow', 3.973],
['allow', 4.444],
['allow', 3.95],
['allow', 4.618]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6002, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [3, 103, 203, 303, 403, 503, 603, 703, 803, 903], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 53, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.465],
['allow', 2.321]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 403, 403], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.962],
['allow', 1.962]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 303, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [86, 138, 254, 788, 1018, 1187, 1336, 1765, 2119, 2249, 2554, 2910],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.377],
['allow', 2.483],
['allow', 2.157],
['allow', 2.771],
['allow', 3.446],
['allow', 4.072],
['allow', 3.274],
['allow', 3.096],
['allow', 3.875],
['allow', 3.664],
['allow', 3.323]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6003, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [4, 104, 204, 304, 404, 504, 604, 704, 804, 904], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 54, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.448],
['allow', 2.322]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 404, 404], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.96],
['allow', 1.96]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 304, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [385, 507, 716, 724, 1100, 1757, 1778, 1945, 2017, 2160, 2509, 2770],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.311],
['allow', 2.208],
['allow', 3.603],
['allow', 3.211],
['allow', 2.183],
['allow', 3.526],
['allow', 4.048],
['allow', 5.01],
['allow', 5.376],
['allow', 4.391],
['allow', 4.217]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6004, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [5, 105, 205, 305, 405, 505, 605, 705, 805, 905], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 55, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.431],
['allow', 2.323]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 405, 405], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.959],
['allow', 1.959]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 305, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [165, 419, 489, 1134, 1196, 1250, 1558, 1747, 2333, 2495, 2720, 2742],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.198],
['allow', 2.444],
['allow', 1.906],
['allow', 3.111],
['allow', 4.255],
['allow', 3.896],
['allow', 4.226],
['allow', 2.797],
['allow', 3.495],
['allow', 3.756],
['allow', 5.046]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6005, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]]]
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 |
|---|---|---|---|
| steady ten per second | [['allow', 0.0], ['allow', 0.952], ['allow', 1.813], ['allow', 2.592], ['allow', 3.297], ['allow', 3.935], ['allow', 4.512], ['allow', 5.034], ['allow', 5.507], ['allow', 5.934]] | [['allow', 0.0], ['allow', 0.952], ['allow', 1.813], ['allow', 2.592], ['allow', 3.297], ['allow', 3.935], ['allow', 4.512], ['allow', 5.034], ['allow', 5.507], ['allow', 5.934]] | Passed |
| burst crosses limit | [['allow', 0.0], ['allow', 1.98], ['allow', 3.921], ['allow', 5.824], ['allow', 7.688], ['allow', 9.499], ['allow', 2.319]] | [['allow', 0.0], ['allow', 1.98], ['allow', 3.921], ['allow', 5.824], ['allow', 7.688], ['allow', 9.499], ['allow', 2.319]] | Passed |
| simultaneous arrivals | [['allow', 0.0], ['allow', 1.106], ['allow', 1.106], ['allow', 1.106], ['allow', 1.969], ['allow', 1.969]] | [['allow', 0.0], ['allow', 1.106], ['allow', 1.106], ['allow', 1.106], ['allow', 1.966], ['allow', 1.966]] | Failed |
| late arrival ignored for clock | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.552], ['allow', 2.177]] | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]] | Failed |
| random arrivals | [['allow', 0.0], ['allow', 1.386], ['allow', 2.293], ['allow', 3.434], ['allow', 4.712], ['allow', 5.987], ['deny', 6.349], ['deny', 6.098], ['allow', 3.332], ['allow', 2.709], ['allow', 4.07], ['allow', 3.19]] | [['allow', 0.0], ['allow', 1.386], ['allow', 2.293], ['allow', 3.434], ['allow', 4.712], ['allow', 5.987], ['deny', 6.349], ['deny', 6.098], ['allow', 3.332], ['allow', 2.709], ['allow', 4.07], ['allow', 3.19]] | Passed |
| slow client | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | Passed |
SHA-256 / f9687aadf16036e6fd9ee7607682c8d90b3ac1ccd6872d7f343449a4a1e88a4d
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
import math
N = 1
observations = []
def solve(x):
tau = x['tau_ms']
lim = x['limit_rps']
r = 0.0
last = None
out = []
for t in x['requests']:
if last is not None and t > last:
dt = t - last
a = math.exp(-dt / tau)
r = a * r + (1 - a) * (1000.0 / dt)
last = t if last is None else max(last, t)
out.append(['deny' if r > lim else 'allow', round(r, 3)])
return out
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['steady ten per second',
{'limit_rps': 12, 'requests': [1, 101, 201, 301, 401, 501, 601, 701, 801, 901], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 51, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.499],
['allow', 2.319]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 401, 401], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.966],
['allow', 1.966]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 301, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [714, 757, 953, 1023, 1049, 1069, 1190, 1379, 2031, 2512, 2526, 2977],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.386],
['allow', 2.293],
['allow', 3.434],
['allow', 4.712],
['allow', 5.987],
['deny', 6.349],
['deny', 6.098],
['allow', 3.332],
['allow', 2.709],
['allow', 4.07],
['allow', 3.19]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6001, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [2, 102, 202, 302, 402, 502, 602, 702, 802, 902], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 52, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.482],
['allow', 2.32]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 402, 402], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.964],
['allow', 1.964]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 302, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [216, 250, 522, 784, 966, 1254, 1553, 2058, 2080, 2239, 2561, 2685],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.394],
['allow', 2.129],
['allow', 2.656],
['allow', 3.306],
['allow', 3.362],
['allow', 3.356],
['allow', 2.649],
['allow', 3.973],
['allow', 4.444],
['allow', 3.95],
['allow', 4.618]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6002, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [3, 103, 203, 303, 403, 503, 603, 703, 803, 903], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 53, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.465],
['allow', 2.321]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 403, 403], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.962],
['allow', 1.962]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 303, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [86, 138, 254, 788, 1018, 1187, 1336, 1765, 2119, 2249, 2554, 2910],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.377],
['allow', 2.483],
['allow', 2.157],
['allow', 2.771],
['allow', 3.446],
['allow', 4.072],
['allow', 3.274],
['allow', 3.096],
['allow', 3.875],
['allow', 3.664],
['allow', 3.323]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6003, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [4, 104, 204, 304, 404, 504, 604, 704, 804, 904], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 54, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.448],
['allow', 2.322]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 404, 404], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.96],
['allow', 1.96]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 304, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [385, 507, 716, 724, 1100, 1757, 1778, 1945, 2017, 2160, 2509, 2770],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.311],
['allow', 2.208],
['allow', 3.603],
['allow', 3.211],
['allow', 2.183],
['allow', 3.526],
['allow', 4.048],
['allow', 5.01],
['allow', 5.376],
['allow', 4.391],
['allow', 4.217]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6004, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]],
[['steady ten per second',
{'limit_rps': 12, 'requests': [5, 105, 205, 305, 405, 505, 605, 705, 805, 905], 'tau_ms': 1000},
[['allow', 0.0],
['allow', 0.952],
['allow', 1.813],
['allow', 2.592],
['allow', 3.297],
['allow', 3.935],
['allow', 4.512],
['allow', 5.034],
['allow', 5.507],
['allow', 5.934]]],
['burst crosses limit',
{'limit_rps': 20, 'requests': [0, 10, 20, 30, 40, 55, 1000], 'tau_ms': 500},
[['allow', 0.0],
['allow', 1.98],
['allow', 3.921],
['allow', 5.824],
['allow', 7.688],
['allow', 9.431],
['allow', 2.323]]],
['simultaneous arrivals',
{'limit_rps': 5, 'requests': [0, 200, 200, 200, 405, 405], 'tau_ms': 800},
[['allow', 0.0],
['allow', 1.106],
['allow', 1.106],
['allow', 1.106],
['allow', 1.959],
['allow', 1.959]]],
['late arrival ignored for clock',
{'limit_rps': 8, 'requests': [0, 500, 305, 700, 900], 'tau_ms': 1000},
[['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]]],
['random arrivals',
{'limit_rps': 6,
'requests': [165, 419, 489, 1134, 1196, 1250, 1558, 1747, 2333, 2495, 2720, 2742],
'tau_ms': 700},
[['allow', 0.0],
['allow', 1.198],
['allow', 2.444],
['allow', 1.906],
['allow', 3.111],
['allow', 4.255],
['allow', 3.896],
['allow', 4.226],
['allow', 2.797],
['allow', 3.495],
['allow', 3.756],
['allow', 5.046]]],
['slow client',
{'limit_rps': 1, 'requests': [0, 3000, 6005, 6500], 'tau_ms': 2000},
[['allow', 0.0], ['allow', 0.259], ['allow', 0.316], ['allow', 0.69]]]]]
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 |
|---|---|---|---|
| steady ten per second | [['allow', 0.0], ['allow', 0.952], ['allow', 1.813], ['allow', 2.592], ['allow', 3.297], ['allow', 3.935], ['allow', 4.512], ['allow', 5.034], ['allow', 5.507], ['allow', 5.934]] | [['allow', 0.0], ['allow', 0.952], ['allow', 1.813], ['allow', 2.592], ['allow', 3.297], ['allow', 3.935], ['allow', 4.512], ['allow', 5.034], ['allow', 5.507], ['allow', 5.934]] | Passed |
| burst crosses limit | [['allow', 0.0], ['allow', 1.98], ['allow', 3.921], ['allow', 5.824], ['allow', 7.688], ['allow', 9.499], ['allow', 2.319]] | [['allow', 0.0], ['allow', 1.98], ['allow', 3.921], ['allow', 5.824], ['allow', 7.688], ['allow', 9.499], ['allow', 2.319]] | Passed |
| simultaneous arrivals | [['allow', 0.0], ['allow', 1.106], ['allow', 1.106], ['allow', 1.106], ['allow', 1.966], ['allow', 1.966]] | [['allow', 0.0], ['allow', 1.106], ['allow', 1.106], ['allow', 1.106], ['allow', 1.966], ['allow', 1.966]] | Passed |
| late arrival ignored for clock | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]] | [['allow', 0.0], ['allow', 0.787], ['allow', 0.787], ['allow', 1.551], ['allow', 2.176]] | Passed |
| random arrivals | [['allow', 0.0], ['allow', 1.386], ['allow', 2.293], ['allow', 3.434], ['allow', 4.712], ['allow', 5.987], ['deny', 6.349], ['deny', 6.098], ['allow', 3.332], ['allow', 2.709], ['allow', 4.07], ['allow', 3.19]] | [['allow', 0.0], ['allow', 1.386], ['allow', 2.293], ['allow', 3.434], ['allow', 4.712], ['allow', 5.987], ['deny', 6.349], ['deny', 6.098], ['allow', 3.332], ['allow', 2.709], ['allow', 4.07], ['allow', 3.19]] | Passed |
| slow client | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | [['allow', 0.0], ['allow', 0.259], ['allow', 0.317], ['allow', 0.689]] | Passed |
SHA-256 / ae9e342895343a060b50275053ac8ec827ac062821b494aaada7838947fc65eb
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:50.709146+00:00.
Case digest / 0e10b6befb08b1ae523e09137ce3851cc9e57eec8ccb3b97eecb775ab6a01114