FA-73509 / Rate limiter algorithms / Member archive

Leaky bucket queue shaper: departure scheduled before arrival · case 04

After an idle period requests are reported as departing before they arrived.

Member previewVariant 4 · 3 implementations · 6 checks per implementation

Case contract

Input {queue_cap, interval_ms, requests [t]} with nondecreasing t. Accepted requests depart one per interval: departure = max(arrival, next_free) and next_free = departure + interval. A request is accepted only while fewer than queue_cap accepted requests have a departure strictly after its arrival; otherwise it is "dropped" and changes nothing. Return each departure time or "dropped".

Why this case matters

Traffic shapers smooth bursts into a steady departure rate; the queue bound and slot arithmetic decide latency and drop behaviour.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
idle line departs immediately	`[0, 50, 100, 150]`	`[1004, 2000, 2050, 5000]`	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.