FA-73566 / Rate limiter algorithms / Open access
AIMD adaptive concurrency limit: successes do not count down the cooldown · case 01
After one loss the limiter ignores later losses until more losses arrive, reacting too slowly.
ROOT CAUSE
Only loss events count down the cooldown.
VERIFIED REPAIR
Count down the cooldown on every event.
Unsuccessful approach: Clearing the cooldown on the first success lets the next loss halve again immediately.
Case contract
Input {initial, min, max, cooldown, events}. The limit is kept in fixed-point thousandths (integer). "ok" adds floor(10^6 / limit_thousandths), i.e. 1/limit, capped at max, and counts down an active cooldown. "drop" or "timeout" halves the limit (floor), floored at min, and starts a cooldown of the given number of events when no cooldown is active; during a cooldown a loss only counts it down. After each event report floor(limit). Return [reported whole limits, final limit in thousandths].
Why this case matters
Adaptive concurrency limiters (AIMD, as in TCP congestion control) protect overloaded backends; step sizes, bounds and cooldowns decide whether the limit converges or oscillates.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
lim = x['initial'] * 1000
lo, hi = x['min'] * 1000, x['max'] * 1000
cool = 0
out = []
for ev in x['events']:
if ev == 'ok':
lim = min(hi, lim + 1000000 // lim)
pass
elif cool == 0:
lim = max(lo, lim // 2)
cool = x['cooldown']
else:
cool -= 1
out.append(lim // 1000)
return [out, lim]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2], 2500]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4595]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4], 4250]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'timeout',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6], 6031]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2], 2900]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4812]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4485]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'ok',
'ok',
'timeout',
'drop',
'timeout',
'drop',
'ok',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 3], 3244]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6], 6196]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3], 3244]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5], 5019]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4707]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'drop',
'ok',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 4, 4, 4, 2], 2305]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6], 6357]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3], 3552]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5], 5218]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4], 4919]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 2], 2496]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6], 6514]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3, 3], 3833]],
['ceiling',
{'cooldown': 1,
'events': ['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5, 5], 5409]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4, 5], 5122]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'timeout',
'timeout',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop',
'ok',
'timeout',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2], 2900]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]]]
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 |
|---|---|---|---|
| additive growth | [[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861] | [[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861] | Passed |
| halving to floor | [[2, 2, 2, 2, 2], 2500] | [[2, 2, 2, 2, 2], 2500] | Passed |
| ceiling | [[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000] | [[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000] | Passed |
| cooldown counts successes | [[8, 8, 8, 8, 8, 8, 8], 8488] | [[8, 8, 8, 4, 4, 4, 4], 4595] | Failed |
| cooldown counts losses | [[8, 8, 8, 4, 4, 4], 4250] | [[8, 8, 8, 4, 4, 4], 4250] | Passed |
| random signals | [[3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 3, 3, 3, 2, 2, 2], 2500] | [[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500] | Failed |
| odd limit halves | [[7, 3, 3, 4, 2], 2055] | [[7, 3, 3, 4, 2], 2055] | Passed |
SHA-256 / ac879f1e7348e1e9b2bdb4c47176af1fedddeac0ab47532594388eef08e03a2f
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
lim = x['initial'] * 1000
lo, hi = x['min'] * 1000, x['max'] * 1000
cool = 0
out = []
for ev in x['events']:
if ev == 'ok':
lim = min(hi, lim + 1000000 // lim)
cool = 0
elif cool == 0:
lim = max(lo, lim // 2)
cool = x['cooldown']
else:
cool -= 1
out.append(lim // 1000)
return [out, lim]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2], 2500]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4595]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4], 4250]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'timeout',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6], 6031]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2], 2900]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4812]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4485]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'ok',
'ok',
'timeout',
'drop',
'timeout',
'drop',
'ok',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 3], 3244]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6], 6196]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3], 3244]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5], 5019]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4707]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'drop',
'ok',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 4, 4, 4, 2], 2305]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6], 6357]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3], 3552]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5], 5218]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4], 4919]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 2], 2496]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6], 6514]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3, 3], 3833]],
['ceiling',
{'cooldown': 1,
'events': ['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5, 5], 5409]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4, 5], 5122]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'timeout',
'timeout',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop',
'ok',
'timeout',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2], 2900]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]]]
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 |
|---|---|---|---|
| additive growth | [[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861] | [[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861] | Passed |
| halving to floor | [[2, 2, 2, 2, 2], 2500] | [[2, 2, 2, 2, 2], 2500] | Passed |
| ceiling | [[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000] | [[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000] | Passed |
| cooldown counts successes | [[8, 8, 8, 4, 4, 2, 2], 2641] | [[8, 8, 8, 4, 4, 4, 4], 4595] | Failed |
| cooldown counts losses | [[8, 8, 8, 4, 4, 4], 4250] | [[8, 8, 8, 4, 4, 4], 4250] | Passed |
| random signals | [[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2000] | [[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500] | Failed |
| odd limit halves | [[7, 3, 3, 4, 2], 2055] | [[7, 3, 3, 4, 2], 2055] | Passed |
SHA-256 / a250bd5207560fdf0c846722f6d9abfe948a96b49982df5babe639e32bd5c9c0
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(x):
lim = x['initial'] * 1000
lo, hi = x['min'] * 1000, x['max'] * 1000
cool = 0
out = []
for ev in x['events']:
if ev == 'ok':
lim = min(hi, lim + 1000000 // lim)
if cool:
cool -= 1
elif cool == 0:
lim = max(lo, lim // 2)
cool = x['cooldown']
else:
cool -= 1
out.append(lim // 1000)
return [out, lim]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2], 2500]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4595]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4], 4250]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'timeout',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6], 6031]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2], 2900]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4812]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4], 4485]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'ok',
'ok',
'timeout',
'drop',
'timeout',
'drop',
'ok',
'ok',
'ok',
'timeout',
'ok',
'drop',
'ok',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 2, 3], 3244]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6], 6196]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3], 3244]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5], 5019]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4], 4707]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'drop',
'ok',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 4, 2, 2, 2, 3, 3, 3, 4, 4, 4, 2], 2305]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6], 6357]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3], 3552]],
['ceiling',
{'cooldown': 1,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5], 5218]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4], 4919]],
['random signals',
{'cooldown': 2,
'events': ['timeout',
'ok',
'drop',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop'],
'initial': 6,
'max': 12,
'min': 2},
[[3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 2], 2496]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4], 4110]]],
[['additive growth',
{'cooldown': 2,
'events': ['ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 4,
'max': 20,
'min': 1},
[[4, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6], 6514]],
['halving to floor',
{'cooldown': 0,
'events': ['drop', 'drop', 'timeout', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 5,
'max': 20,
'min': 2},
[[2, 2, 2, 2, 2, 2, 3, 3, 3], 3833]],
['ceiling',
{'cooldown': 1,
'events': ['ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok',
'ok'],
'initial': 9,
'max': 10,
'min': 1},
[[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10], 10000]],
['cooldown counts successes',
{'cooldown': 2,
'events': ['drop', 'ok', 'ok', 'drop', 'ok', 'drop', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 5, 5, 5], 5409]],
['cooldown counts losses',
{'cooldown': 2,
'events': ['drop', 'drop', 'drop', 'drop', 'timeout', 'ok', 'ok', 'ok', 'ok', 'ok'],
'initial': 16,
'max': 32,
'min': 1},
[[8, 8, 8, 4, 4, 4, 4, 4, 4, 5], 5122]],
['random signals',
{'cooldown': 2,
'events': ['ok',
'timeout',
'timeout',
'ok',
'ok',
'ok',
'timeout',
'ok',
'ok',
'ok',
'ok',
'ok',
'drop',
'ok',
'timeout',
'ok'],
'initial': 6,
'max': 12,
'min': 2},
[[6, 3, 3, 3, 3, 3, 2, 2, 2, 3, 3, 3, 2, 2, 2, 2], 2900]],
['odd limit halves',
{'cooldown': 0, 'events': ['ok', 'drop', 'ok', 'ok', 'drop'], 'initial': 7, 'max': 10, 'min': 1},
[[7, 3, 3, 4, 2], 2055]]]]
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 |
|---|---|---|---|
| additive growth | [[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861] | [[4, 4, 4, 4, 5, 5, 5, 5, 5], 5861] | Passed |
| halving to floor | [[2, 2, 2, 2, 2], 2500] | [[2, 2, 2, 2, 2], 2500] | Passed |
| ceiling | [[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000] | [[9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10], 10000] | Passed |
| cooldown counts successes | [[8, 8, 8, 4, 4, 4, 4], 4595] | [[8, 8, 8, 4, 4, 4, 4], 4595] | Passed |
| cooldown counts losses | [[8, 8, 8, 4, 4, 4], 4250] | [[8, 8, 8, 4, 4, 4], 4250] | Passed |
| random signals | [[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500] | [[3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2], 2500] | Passed |
| odd limit halves | [[7, 3, 3, 4, 2], 2055] | [[7, 3, 3, 4, 2], 2055] | Passed |
SHA-256 / d1b5fec9294aa93ab248712334ae5a8b42c18650de1284eea8f8553934e939d5
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:48.796010+00:00.
Case digest / b368569c2b1cf7b5bd35499f60a75ffe37767579a61e4669917ed2de0c4fb1ae