FAILURE MAP
← Case archive

FA-73661 / Rate limiter algorithms / Open access

Reservation limiter with stored permits: idle resync leaves next_free in the past · case 01

Idle time is credited again at the next request and fresh permits are scheduled in the past.

Verified by executionVariant 1 · 6 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

After converting idle time into stored permits, next_free is not moved to now.

VERIFIED REPAIR

Move next_free to the current time after resynchronising.

Unsuccessful approach: Moving next_free one interval past now imposes a spurious wait after idleness.

Case contract

Input {rate (permits per second), max_burst_s, requests [[t_ms, permits]]} with nondecreasing t. The interval is I = 1000/rate ms. When t is past next_free, idle time is converted into stored permits (capped at max_burst_s*rate) and next_free moves to t. A request waits max(0, next_free - t), i.e. it pays for the previous reservation, then consumes stored permits first and pushes next_free by I per fresh permit. Return [ceil waits in ms, stored, next_free] with exact fractions as strings.

Why this case matters

Client-side reservation limiters (as in smooth-bursty designs) let a large request proceed now and make the next caller wait; getting who pays wrong starves or floods the backend.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(max_stored, stored + (t - next_free) / I)
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        stored -= use
        out.append(math.ceil(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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 fixtureActualExpectedOutcome
pay later for big request[[0, 2000, 2099, 0], '0', '2600'][[0, 2000, 2099, 0], '0', '5200']Failed
stored permits capped[[0, 0, 0, 0], '1', '1000'][[0, 0, 500, 999], '0', '11500']Failed
stored permits consumed[[0, 0, 0, 0], '7', '250'][[0, 0, 0, 499], '0', '3750']Failed
resync after idle[[0, 0, 0, 0, 0], '5', '1000/3'][[0, 0, 0, 0, 0], '3', '4001']Failed
fractional waits[[0, 334, 656, 980], '0', '5000/3'][[0, 334, 656, 980], '0', '5000/3']Passed
random acquires[[0, 0, 1293, 2042, 3539, 4043, 4525, 6191, 7042], '0', '11132'][[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']Failed

SHA-256 / 3a9c9fd05d0498cc478c61ee94fc12e814cc09f59b2555ccff3f3111118bec01

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(max_stored, stored + (t - next_free) / I)
            next_free = Fraction(t) + I
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        stored -= use
        out.append(math.ceil(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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 fixtureActualExpectedOutcome
pay later for big request[[0, 2000, 2099, 200], '0', '5400'][[0, 2000, 2099, 0], '0', '5200']Failed
stored permits capped[[0, 500, 1000, 1499], '0', '12000'][[0, 0, 500, 999], '0', '11500']Failed
stored permits consumed[[0, 250, 250, 749], '0', '4000'][[0, 0, 0, 499], '0', '3750']Failed
resync after idle[[0, 334, 234, 334, 334], '2003/1000', '13003/3'][[0, 0, 0, 0, 0], '3', '4001']Failed
fractional waits[[0, 334, 656, 980], '0', '5000/3'][[0, 334, 656, 980], '0', '5000/3']Passed
random acquires[[500, 852, 2661, 3410, 4907, 5411, 5893, 7559, 8410], '0', '12500'][[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']Failed

SHA-256 / 603274ca14f317bceeeceed4923e3548e251f8ea7800a5b704d01f9b979ea48a

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
import math
from fractions import Fraction
N = 1
observations = []
def solve(x):
    rate = x['rate']
    I = Fraction(1000, rate)
    max_stored = Fraction(x['max_burst_s'] * rate)
    stored = Fraction(0)
    next_free = Fraction(0)
    out = []
    for t, p in x['requests']:
        if t > next_free:
            stored = min(max_stored, stored + (t - next_free) / I)
            next_free = Fraction(t)
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        stored -= use
        out.append(math.ceil(wait))
    return [out, str(stored), str(next_free)]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
cases = [[['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [101, 1], [5000, 1]]},
   [[0, 2000, 2099, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10001, 1]]},
   [[0, 0, 500, 999], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3001, 1]]},
   [[0, 0, 0, 499], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4001, 2], [4001, 4]]},
   [[0, 0, 0, 0, 0], '3', '4001']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [11, 1], [20, 2]]},
   [[0, 334, 656, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[610, 3],
                 [1148, 4],
                 [1339, 3],
                 [2090, 3],
                 [2093, 2],
                 [2589, 1],
                 [2607, 4],
                 [2941, 2],
                 [3090, 2]]},
   [[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [102, 1], [5000, 1]]},
   [[0, 2000, 2098, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10002, 1]]},
   [[0, 0, 500, 998], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3002, 1]]},
   [[0, 0, 0, 498], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4002, 2], [4002, 4]]},
   [[0, 0, 0, 0, 0], '3', '4002']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [12, 1], [20, 2]]},
   [[0, 334, 655, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[142, 4],
                 [325, 1],
                 [548, 2],
                 [901, 1],
                 [1366, 1],
                 [1827, 2],
                 [1998, 3],
                 [2374, 1],
                 [2914, 2]]},
   [[0, 1675, 1952, 2599, 2634, 2673, 3502, 4626, 4586], '0', '8500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [103, 1], [5000, 1]]},
   [[0, 2000, 2097, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10003, 1]]},
   [[0, 0, 500, 997], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3003, 1]]},
   [[0, 0, 0, 497], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4003, 2], [4003, 4]]},
   [[0, 0, 0, 0, 0], '3', '4003']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [13, 1], [20, 2]]},
   [[0, 334, 654, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[644, 4],
                 [886, 4],
                 [910, 3],
                 [1485, 1],
                 [1585, 2],
                 [1776, 4],
                 [2163, 2],
                 [2628, 3],
                 [2698, 2]]},
   [[0, 1114, 3090, 4015, 4415, 5224, 6837, 7372, 8802], '0', '12500']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [104, 1], [5000, 1]]},
   [[0, 2000, 2096, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10004, 1]]},
   [[0, 0, 500, 996], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3004, 1]]},
   [[0, 0, 0, 496], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4004, 2], [4004, 4]]},
   [[0, 0, 0, 0, 0], '3', '4004']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [14, 1], [20, 2]]},
   [[0, 334, 653, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[106, 2],
                 [1122, 1],
                 [1604, 3],
                 [1998, 1],
                 [2099, 1],
                 [2549, 2],
                 [2752, 1],
                 [2983, 1],
                 [3690, 4]]},
   [[0, 0, 0, 1002, 1401, 1451, 2248, 2517, 2310], '0', '8000']]],
 [['pay later for big request',
   {'max_burst_s': 0, 'rate': 5, 'requests': [[0, 10], [0, 1], [105, 1], [5000, 1]]},
   [[0, 2000, 2095, 0], '0', '5200']],
  ['stored permits capped',
   {'max_burst_s': 1, 'rate': 2, 'requests': [[0, 1], [10000, 3], [10000, 1], [10005, 1]]},
   [[0, 0, 500, 995], '0', '11500']],
  ['stored permits consumed',
   {'max_burst_s': 2, 'rate': 4, 'requests': [[0, 1], [3000, 5], [3000, 5], [3005, 1]]},
   [[0, 0, 0, 495], '0', '3750']],
  ['resync after idle',
   {'max_burst_s': 3, 'rate': 3, 'requests': [[0, 1], [2000, 1], [2100, 1], [4005, 2], [4005, 4]]},
   [[0, 0, 0, 0, 0], '3', '4005']],
  ['fractional waits',
   {'max_burst_s': 0, 'rate': 3, 'requests': [[0, 1], [0, 1], [15, 1], [20, 2]]},
   [[0, 334, 652, 980], '0', '5000/3']],
  ['random acquires',
   {'max_burst_s': 2,
    'rate': 2,
    'requests': [[2392, 4],
                 [2748, 2],
                 [3147, 1],
                 [3291, 2],
                 [3293, 2],
                 [3431, 2],
                 [3441, 1],
                 [3672, 1],
                 [3732, 4]]},
   [[0, 0, 245, 601, 1599, 2461, 3451, 3720, 4160], '0', '9892']]]]
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 fixtureActualExpectedOutcome
pay later for big request[[0, 2000, 2099, 0], '0', '5200'][[0, 2000, 2099, 0], '0', '5200']Passed
stored permits capped[[0, 0, 500, 999], '0', '11500'][[0, 0, 500, 999], '0', '11500']Passed
stored permits consumed[[0, 0, 0, 499], '0', '3750'][[0, 0, 0, 499], '0', '3750']Passed
resync after idle[[0, 0, 0, 0, 0], '3', '4001'][[0, 0, 0, 0, 0], '3', '4001']Passed
fractional waits[[0, 334, 656, 980], '0', '5000/3'][[0, 334, 656, 980], '0', '5000/3']Passed
random acquires[[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000'][[0, 352, 2161, 2910, 4407, 4911, 5393, 7059, 7910], '0', '12000']Passed

SHA-256 / b798c6d97203ed2d5704773d4a8bb502d77df750b3c29bb6f94eddd87cdd2dcb

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:49.557617+00:00.

Case digest / 1b80ed5092fe134dbb85445de79cf8321360aa1d09e9ecb62b2ab777b365ff8e