Capped Exponential Backoff Schedule

1. Background Knowledge

Exponential Backoff is a standard algorithm used in distributed systems to manage retry logic when a service is unavailable. Instead of retrying immediately, the client waits for an increasing amount of time between attempts. This prevents "thundering herd" scenarios where multiple clients overwhelm a recovering service. The delay typically grows exponentially: $delay_i = base \times factor^i$. However, unbounded growth is dangerous; therefore, a cap (max_delay) is applied so the delay never exceeds a reasonable threshold.

In HTTP protocols, status codes dictate behavior. 2xx codes indicate success. 429 (Too Many Requests) and 5xx (Server Errors) are generally transient and retryable. Crucially, other 4xx codes (like 400 Bad Request or 404 Not Found) indicate client-side errors. Retrying these is futile and wastes resources, so the process should terminate immediately with a "failed" outcome.

The problem requires simulating this loop. Key constraints include:

1. No sleep after the final attempt: If you succeed or fail on the last allowed attempt, you do not wait.
2. Status Reuse: If the statuses list is shorter than max_attempts, the last status repeats.
3. Rounding: Delays and total wait times must be rounded to 3 decimal places.

2. Algorithm Approach

The solution follows a simulation pattern. You will iterate through attempts from $0$ to max_attempts - 1. In each iteration, you determine the current HTTP status, decide whether to stop or continue, and if continuing, calculate the delay for the next attempt.

The core logic revolves around a while or for loop that tracks:

• Current attempt index.
• Accumulated delays.
• Current outcome state.

You must carefully distinguish between the action taken after an attempt (checking status) and the action taken before the next attempt (sleeping). The delay is associated with the transition from attempt $i$ to $i+1$.

3. Step-by-Step Strategy

1. Initialize Variables: Create a list for delays, a counter for attempts, and a variable for total_wait. Set outcome to None.
2. Loop Through Attempts: Iterate i from $0$ to max_attempts - 1.

• Get Status: Retrieve the status code. If i is within the bounds of statuses, use statuses[i]. Otherwise, use the last element of statuses.
• Check Outcome:
• If status is 2xx: Set outcome to "success", increment attempts, and break the loop. No delay is added after success.
• If status is 4xx (but not 429): Set outcome to "failed", increment attempts, and break. No delay is added after a client error.
• If status is 429 or 5xx: This is a retryable error.
• Increment attempts.
• Check if more attempts are allowed: If i < max_attempts - 1, calculate the delay for the next retry.
• Calculate raw delay: $raw = base\_delay \times factor^i$.
• Apply cap: $delay = \min(raw, max\_delay)$.
• Round to 3 decimals and append to delays.
• Add to total_wait.
• If i == max_attempts - 1 (this is the last attempt), do not add a delay. After this iteration, the loop ends, and the outcome becomes "exhausted".

3. Handle Exhaustion: If the loop completes without breaking (i.e., all max_attempts were used and the last one was retryable), set outcome to "exhausted".
4. Finalize: Round total_wait to 3 decimals. Return the dictionary with attempts, delays, total_wait, and outcome.

4. Common Pitfalls

• Off-by-One in Delays: The most common error is adding a delay after the final attempt. Remember: you only sleep if you are going to try again. If you succeed or fail on the last attempt, the process ends immediately.
• Indexing for Delay Calculation: The formula uses $i$ (0-based attempt index). Ensure you use the index of the current failed attempt to calculate the delay before the next attempt. For example, after the 1st attempt ($i=0$) fails, the delay is $base \times factor^0$.
• Status Code Classification: Ensure you correctly identify 429 as retryable. Many developers mistakenly treat all 4xx as non-retryable, but 429 is an exception.
• Rounding Errors: Floating-point arithmetic can introduce small errors. Apply round(value, 3) to each delay individually before summing, and round the final sum again, as specified.
• Empty Statuses List: The problem states statuses is non-empty, but ensure your logic handles the case where len(statuses) < max_attempts by repeating the last status.

5. Time & Space Complexity

• Time Complexity: $O(N)$, where $N$ is max_attempts. The loop runs at most max_attempts times. Each iteration performs constant-time operations (math, list access, comparisons).
• Space Complexity: $O(N)$, where $N$ is max_attempts. In the worst case (all attempts fail and are retryable), the delays list will store up to max_attempts - 1 elements. The output dictionary also stores this list.