FA-73668 / Rate limiter algorithms / Member archive

Reservation limiter with stored permits: wait truncated · case 03

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

Member previewVariant 3 · 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
fractional waits	`[[0, 333, 653, 980], "0", "5000/3"]`	`[[0, 334, 654, 980], "0", "5000/3"]`	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.