FA-73515 / Rate limiter algorithms / Member archive

Leaky bucket queue shaper: request departing now counted as queued · case 05

A request arriving at the same instant another departs is dropped.

Member previewVariant 5 · 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
burst queues then drops	`[0, 100, "dropped", "dropped", 200, 400]`	`[0, 100, 200, "dropped", 300, 400]`	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.