Exponential Backoff & Jitter

The problem, from first principles

Tool calls fail for transient reasons: a rate limit, a timeout, an overloaded server. Retrying immediately usually fails again and, worse, a crowd of clients retrying in lockstep keeps the server overloaded. The standard remedy is exponential backoff: wait base, then base * factor, then base * factor^2, up to a cap, so the load on the struggling service falls quickly. Adding jitter, a random fraction of the delay, desynchronizes clients so that they do not all return at the same instant. "Full jitter" waits a uniformly random time between 0 and the capped delay.

From theory to code

Implement backoff_delays and total_wait.

Constraints

• backoff_delays(n_retries, base, factor, cap, rng=None) returns a list of n_retries waiting times. Retry k (starting at 0) has capped = min(cap, base * factor ** k).
• If rng is None the delay is capped. Otherwise it is full jitter: capped * rng.random(), with exactly one rng.random() call per retry in order (rng is a random.Random).
• total_wait(delays) returns the sum as a float.

Hints