FAILURE MAP
← Case archive

FA-73666 / Rate limiter algorithms / Open access

Reservation limiter with stored permits: wait truncated · case 01

Callers sleep slightly too little and run ahead of the configured rate.

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

ROOT CAUSE

The fractional wait is truncated instead of rounded up.

VERIFIED REPAIR

Round the wait up to whole milliseconds.

Unsuccessful approach: Rounding to nearest still shortens waits with small fractions.

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)
            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(int(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, 333, 655, 980], '0', '5000/3'][[0, 334, 656, 980], '0', '5000/3']Failed
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 / 51847578b31306c4f773b1d1ea2593d586785ac8f932d64223377df35457bb8e

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)
        wait = max(Fraction(0), next_free - t)
        use = min(Fraction(p), stored)
        fresh = p - use
        next_free += fresh * I
        stored -= use
        out.append(round(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, 333, 656, 980], '0', '5000/3'][[0, 334, 656, 980], '0', '5000/3']Failed
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 / 819c0a16b3a3d2502064de6c1786cc58b432afa4543bdbbb9b835a1826fcf248

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

Case digest / 3a6bf490098f0c3010c9fa818b0c0a7af9ac49fb8a1913ff2ddcc924d767aa1b