Exponential Backoff Schedule with Jitter Bounds

easyFREEReliability & Failure HandlingAI AgentsAI Agents 1

Problem Statement

A tool returns 429. The agent retries immediately, gets another 429, retries again - and a transient blip becomes a self-inflicted outage, with every concurrent agent hammering in lockstep. Exponential backoff spaces the retries out; jitter breaks the lockstep. Before shipping either, you want to know the actual numbers: how long the worst case takes, and when the growth flattens against the cap.

Background

For a 0-based attempt index $i$ , the nominal delay is

$d_i = \min(\text{cap},\ \text{base} \cdot \text{factor}^{\,i})$

Jitter turns each fixed delay into a range. With a jitter fraction $j \in [0, 1]$ the actual sleep is drawn uniformly from

$[\,d_i (1 - j),\ d_i\,]$

so $j = 0$ is no jitter, $j = 0.5$ is "equal jitter" and $j = 1$ is "full jitter" (the range starts at zero). You are computing the deterministic bounds, not sampling - the schedule must be reproducible.

Your Task

Implement:

def backoff_schedule(base, factor, cap, attempts, jitter):

Return a dict:

delays: list of [lo, hi] pairs, one per attempt, each rounded to 4 decimal places.
best_case_total: sum of the (already rounded) lo values, rounded to 4 dp.
worst_case_total: sum of the (already rounded) hi values, rounded to 4 dp.
capped_at: the smallest 0-based attempt index whose uncapped delay base * factori** is >= cap, or -1 if the cap is never reached within attempts.

Input/Output Format

All floats are rounded to 4 decimal places. capped_at is an int. With attempts = 0, delays is empty and both totals are 0.0.

Sample

print(backoff_schedule(1.0, 2.0, 8.0, 5, 0.5)["delays"])
# [[0.5, 1.0], [1.0, 2.0], [2.0, 4.0], [4.0, 8.0], [4.0, 8.0]]

Delays double until they hit the 8.0 cap at attempt 3, and equal jitter puts the lower bound at half of each.

Example

Input

print(backoff_schedule(1.0, 2.0, 8.0, 5, 0.5)['delays'])

Output

[[0.5, 1.0], [1.0, 2.0], [2.0, 4.0], [4.0, 8.0], [4.0, 8.0]]

Reasoning

Inputs: base $= 1.0$ s is the first delay, factor $= 2.0$ doubles it each attempt, cap $= 8.0$ s is the ceiling, attempts $= 5$ asks for five delays (indices $i = 0$ to $4$ ), and jitter $= 0.5$ is equal jitter.
Uncapped growth: $\text{base} \cdot \text{factor}^i$ gives $1, 2, 4, 8, 16$ seconds. Attempt $3$ is the first where this reaches the cap ( $8 \ge 8$ ), so the capped-at index is $3$ .
Apply the cap: $d_i = \min(8, \cdot)$ leaves $1, 2, 4, 8$ alone and pulls $16$ down to $8$ . These are the upper bounds of each range.
Lower bounds: $d_i(1 - 0.5) = d_i / 2$ gives $0.5, 1, 2, 4, 4$ . Pairing each lower bound with its $d_i$ yields [[0.5, 1.0], [1.0, 2.0], [2.0, 4.0], [4.0, 8.0], [4.0, 8.0]].
Totals: best case $0.5 + 1 + 2 + 4 + 4 = 11.5$ s, worst case $1 + 2 + 4 + 8 + 8 = 23.0$ s.
Notice the last two pairs are identical: once the cap bites, extra attempts add a flat $8$ s each instead of doubling. Full jitter would make every lower bound $0$ .

Constraints

base > 0, factor >= 1.0, cap > 0, 0 <= attempts <= 64, 0 <= jitter <= 1
Attempt indices are 0-based: the first delay is base * factor**0 = base
Every delay bound is rounded to 4 decimal places
Totals are the sums of the already-rounded bounds, rounded again to 4 dp
capped_at compares the uncapped delay against cap using >=
Never emit a raw unrounded float

Learn this in

Multi-Agent Coordination & Failure ModesAgent Engineering Study Plan

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium

Concept primer

1. Background Knowledge

Exponential backoff is a standard algorithm used in distributed systems and network protocols to handle transient failures. When a request fails (e.g., HTTP 429 Too Many Requests), the client waits before retrying. The wait time increases exponentially with each subsequent attempt (e.g., 1s, 2s, 4s, 8s). This prevents overwhelming the server with immediate retries and allows the system time to recover. However, if many clients use the same deterministic backoff schedule, they may all retry at the exact same moment, causing a "thundering herd" problem.

To mitigate this synchronization issue, jitter is introduced. Jitter adds randomness to the wait time, spreading out the retry attempts. In this problem, we are not simulating random sampling but calculating the deterministic bounds of that randomness. With a jitter fraction $j$ , the actual delay for a nominal delay $d$ is uniformly distributed in the range $[d(1-j), d]$ . This means the minimum possible delay (best case) is $d(1-j)$ and the maximum possible delay (worst case) is $d$ .

The cap is a maximum limit on the delay to prevent waiting indefinitely. Once the exponential growth exceeds this cap, the delay stays constant at the cap value. Understanding how to calculate when this cap is first reached is crucial for determining the capped_at index. This involves solving for the smallest integer $i$ such that $\text{base} \cdot \text{factor}^i \ge \text{cap}$ .

2. Algorithm Approach

The core approach is iterative simulation with boundary tracking. Since the number of attempts is typically small in these scenarios, we can iterate through each attempt index $i$ from $0$ to $\text{attempts} - 1$ . For each index, we calculate the nominal delay, apply the cap, and then compute the jitter bounds.

We need to maintain two accumulators: one for the sum of lower bounds (best_case_total) and one for the sum of upper bounds (worst_case_total). We also need a flag or variable to track the first index where the uncapped delay meets or exceeds the cap. The algorithm processes each attempt sequentially, updating the state and storing the results in a list.

3. Step-by-Step Strategy

Initialize Variables: Create an empty list delays to store [lo, hi] pairs. Initialize best_case_total and worst_case_total to $0.0$ . Set capped_at to $-1$ .
Handle Edge Case: If attempts is $0$ , return the dictionary with empty delays and totals of $0.0$ .
Iterate Through Attempts: Loop $i$ from $0$ to attempts - $1$ :

Calculate the uncapped nominal delay: $d_{\text{uncapped}} = \text{base} \cdot \text{factor}^i$ .
Check for Cap: If capped_at is still $-1$ and $d_{\text{uncapped}} \ge \text{cap}$ , set capped_at to $i$ .
Calculate the capped nominal delay: $d = \min(\text{cap}, d_{\text{uncapped}})$ .
Calculate Jitter Bounds:
Lower bound: $lo = d \cdot (1 - \text{jitter})$
Upper bound: $hi = d$
Round Values: Round $lo$ and $hi$ to 4 decimal places.
Accumulate Totals: Add the rounded $lo$ to best_case_total and the rounded $hi$ to worst_case_total.
Store Result: Append [lo, hi] to the delays list.

Final Rounding: Round best_case_total and worst_case_total to 4 decimal places.
Return Result: Construct and return the dictionary with delays, best_case_total, worst_case_total, and capped_at.

4. Common Pitfalls

Rounding Order: The problem specifies that delays are rounded to 4 decimal places before summing. Do not sum the raw floats and then round the total. You must round each individual $lo$ and $hi$ first, then sum those rounded values, and finally round the totals.
Cap Comparison: Ensure you compare the uncapped delay against the cap to determine capped_at. If you compare the capped delay, it will always be $\le \text{cap}$ , making the logic incorrect. The condition is $d_{\text{uncapped}} \ge \text{cap}$ .
Floating Point Precision: Be cautious with floating-point arithmetic. While Python handles floats well, explicit rounding at each step as required by the problem is critical. Using round(value, 4) is the standard approach.
Zero Attempts: Always check if attempts is $0$ at the start. The loop should not execute, and the totals should remain $0.0$ .
Jitter Range: Remember that the upper bound is always the full nominal delay $d$ , not $d(1+j)$ . The jitter only reduces the delay from the nominal value, it does not increase it.

5. Time & Space Complexity

Time Complexity: $O(N)$ , where $N$ is the number of attempts. We perform a constant amount of arithmetic operations for each attempt. The exponentiation factori** can be computed iteratively (multiplying by factor each step) to maintain $O(1)$ per step, or directly as $O(1)$ if the exponent is small.
Space Complexity: $O(N)$ to store the delays list, which contains $N$ pairs of floats. The auxiliary space for variables is $O(1)$ .

solution.py

Python 3.13

Test results