FA-73571 / Rate limiter algorithms / Open access
AIMD adaptive concurrency limit: losses during cooldown do not count it down · case 01
A sustained burst of losses keeps the limiter in cooldown and prevents any further decrease.
ROOT CAUSE
Loss events during the cooldown leave the counter unchanged.
VERIFIED REPAIR
Count down the cooldown for losses as well.
Unsuccessful approach: Restarting the cooldown on each loss suppresses decreases for as long as losses continue.
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)
if cool:
cool -= 1
elif cool == 0:
lim = max(lo, lim // 2)
cool = x['cooldown']
else:
pass
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, 8, 8, 8], 8125] | [[8, 8, 8, 4, 4, 4], 4250] | Failed |
| random signals | [[3, 3, 3, 3, 3, 3, 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] | Failed |
| odd limit halves | [[7, 3, 3, 4, 2], 2055] | [[7, 3, 3, 4, 2], 2055] | Passed |
SHA-256 / 4afc602b8606fcbbde4a7716415bacb4f43ffe2bed2ccab2f988d4dff561c152
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)
if cool:
cool -= 1
elif cool == 0:
lim = max(lo, lim // 2)
cool = x['cooldown']
else:
cool = x['cooldown']
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, 8, 8, 8], 8125] | [[8, 8, 8, 4, 4, 4], 4250] | Failed |
| random signals | [[3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3], 3244] | [[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 / b77bff9463efe047727412e9e182a2f1a3d4cf6a331baf79cbd1ec2c1626e1b5
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.796658+00:00.
Case digest / c3dbf44fce5015fb866cb77eda3c7b4bf1caff192f8cfea53177d8c94f15b55a