FA-73478 / Rate limiter algorithms / Member archive

Sliding-window counter approximation: elapsed measured from the previous window · case 03

The first request of a new window computes a negative overlap and under-counts.

Member previewVariant 3 · 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", "-3/250"], ["allow", "4"], ["allow", "4"], ["deny", "19/5"]], [1, 4, 3]]`	`[[["allow", "1"], ["allow", "2"], ["allow", "3"], ["allow", "4"], ["allow", "997/250"], ["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.