FA-73827 / Rate limiter algorithms / Member archive

Max-min fair split of a global rate limit: allocation exceeds demand · case 02

Light clients receive rate they cannot use while heavy clients are starved.

Member previewVariant 2 · 3 implementations · 10 checks per implementation

Case contract

Input {capacity, demands [[client, demand]]} in integer requests per second. Clients with positive demand are active. Repeatedly give each active client min(floor(left / active count), unmet demand) and drop satisfied clients; when the per-client share rounds to zero, hand single units to active clients in ascending id order until capacity is exhausted. Return [sorted [client, allocation]], unallocated capacity].

Why this case matters

Distributed limiters split a global rate among clients or nodes by max-min fairness so light users are fully served and heavy users share the rest.

One recorded failure

Sample boundary fixture

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

Boundary fixture	Actual	Expected	Outcome
small demand satisfied first	`[[["a", 3], ["b", 4], ["c", 3]], 0]`	`[[["a", 2], ["b", 4], ["c", 4]], 0]`	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.