FA-73472 / Rate limiter algorithms / Member archive

Sliding-window counter approximation: fractional estimate admits over the limit · case 02

An estimate of 3.5 against a limit of 4 is admitted, pushing the rolling rate over the limit.

Member previewVariant 2 · 3 implementations · 7 checks per implementation

Case contract

Input {limit, window_ms, requests [t]} with nondecreasing t. Keep counts for the current and previous epoch windows; moving to the next window rotates cur into prev, skipping more than one window clears both. The estimate is prev * (W - elapsed)/W + cur with elapsed = t - window start, exactly. Allow when est + 1 <= limit (reporting est + 1), else deny (reporting est). Return [[decision, estimate as fraction string]], [window, prev, cur]].

Why this case matters

Edge proxies approximate a rolling window with two counters; the weighting and rotation rules determine whether boundary bursts are smoothed or doubled.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
previous window weighting	`[[["allow", "1"], ["allow", "2"], ["allow", "3"], ["allow", "4"], ["allow", "499/125"], ["allow", "4"], ["allow", "4"], ["allow", "24/5"]], [1, 4, 4]]`	`[[["allow", "1"], ["allow", "2"], ["allow", "3"], ["allow", "4"], ["allow", "499/125"], ["allow", "4"], ["allow", "4"], ["deny", "19/5"]], [1, 4, 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.