FA-73654 / Rate limiter algorithms / Member archive

Reservation limiter with stored permits: stored permits unbounded · case 04

After a long idle period the limiter releases an arbitrarily large burst.

Member previewVariant 4 · 3 implementations · 6 checks per implementation

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.

One recorded failure

Sample boundary fixture

This sample comes from the broken implementation of a controlled reproducer.

Boundary fixture	Actual	Expected	Outcome
pay later for big request	`[[0, 2000, 2096, 0], "12", "5000"]`	`[[0, 2000, 2096, 0], "0", "5200"]`	Failed

MEMBER ARCHIVE

The complete case is available to members.

This record includes three runnable implementations, regression fixtures, execution results, and source hashes.

Member access is invitation-based. Sign in with your invited account to inspect the sources.