How far over its limit can a rate limiter be pushed in a true rolling window?

research/ratelimit-burst

How far over its limit can a rate limiter be pushed in a true rolling window? Adversarial search over fixed window, sliding log, sliding-window counter, token bucket and leaky bucket: only the sliding log holds the limit; the sliding counter admits up to about 1.5 L and the buckets nearly 2 L, and under Poisson overload at 1.5x load 39-47% of rolling windows exceed the limit for fixed window and buckets. Stylised.

7 tests

What it found

A stylised free-choice study of five limiters configured as L requests per window W, by adversarial search on an integer tick clock and a Poisson overload test. Only the sliding log never admits more than L in a rolling window. The sliding-window counter admits up to about 1.4–1.5L (1.40, 1.45, 1.48 for W = 20, 40, 100), and token and leaky buckets admit 1.90–1.98L; fixed window reaches 2L. At 1.5× offered Poisson load, 47% of rolling windows exceed L for fixed window, 39% for the buckets, 8.8% for the sliding counter and none for the sliding log. The searches give lower bounds, not proofs; one client, no distributed state.

Paper, code and results

More in Decentralised training systems

What can one stubborn node do to gossip training?Pairwise gossip for decentralised training: exact contraction (n−2)/(2(n−1))≈½ per matching round (~20 rounds at any n), noise floor (n−1)(n−2)s²/n, one stubborn node captures consensus at rate 1−1/(n(n−1)), trust-region clipping caps drift at τ/(n(n−1)) per step.
What does infrequent averaging do to the answer?Local-SGD/DiLoCo-style averaging on heterogeneous quadratics: exact fixed point with saturating weights 1-(1-ηa_i)^H, non-monotone bias to the unweighted mean, exact a_i/w_i correction, step-count inflation moves the fixed point 0.50→0.91, wall-clock-optimal sync interval.
How often should preemptible workers checkpoint?Checkpoint interval for preemptible decentralised training: exact Lambert-W optimum independent of restart cost, Young/Daly overshoot 5–25%, flat within 2×, synchronous efficiency wall (50% at n≈691), flaky workers cut throughput 5×.
Should a pipeline replicate stages or skip them?Replicate or skip? pipeline stages on unreliable workers: exact binomial drop law, replicas cannot beat the shared-domain floor (1−ρ)^L, a 4-stage skip budget halves workers for a 1e-3 drop rate (240 → 96), cost-optimal design shifts from skipping to replication as skips get costly.
How should a model be cut across devices of unequal speed?Cutting a model across heterogeneous devices: exact greedy bottleneck partition (matches DP, with memory caps), W/V ≤ T* < W/V + m·w_max/V, speed-blind splitting costs exactly v̄/v_min (2.4× at σ=0.5), device order is the residual decision (sorts no better than arbitrary, swap search within 1.1%), memory inverse to speed costs 1.7×.
What does it cost to skip the slowest workers?Waiting for the fastest k of n workers: exact order-statistic round times (Pareto mean finite iff n−k+1 > 1/α), exact SGD time-to-accuracy with a minimum k and an interior optimum (34× over wait-for-all at s=0, 1.12× at s=32), joint step tuning, and the exact selection bias of the speed filter with Horvitz–Thompson correction.

All 23 Decentralised training systems projects →

Other research topics

Proper scoring & elicitation28 Effort & peer prediction9 Verification games & slashing19 Detection & tolerances14 Markets as routers13 Prediction-market design9 Paying contributors8 Decentralised training systems23 Digital twins & sim-to-real164 LLM chip design loops40 Robot manufacturing loops53 Ambient AI assistant46 Self-replicating manufacturing34 Simulation-first design64 Engineered clothing45 Task-specific AI accelerators40 Algorithmic chip-design loops42 Open-source purpose-built robots44 The software-engineering loop43 Adversarial human imitation41 Open-source residential construction41 Autonomous multi-angle capture34 Sensing, imaging and 3D31 Energy supply and dense energy storage39 Robot societies among people31 Agentic co-design of low-cost robots27 Laundry-hanging robots25 Machine learning on qualitative data23 Robots on the building site27 Civilizations & group psychology1 History & human sciences1

Produced with AI assistance (Claude). Results are from the code in this repository and are simulated or stylised unless the abstract says otherwise; nothing here implies affiliation with or endorsement by any lab, researcher or company cited. MIT licensed.