Total Retry Latency with Capped Backoff
Problem Statement
An agent retries a failing call with exponential backoff. Compute the total wall-clock delay spent sleeping between attempts, given a cap on each individual backoff.
Background
With base seconds, factor 2, and attempts total tries, the sleeps happen between attempts: after attempt i (1-indexed) the agent sleeps min(base * 2(i-1), cap)** seconds, for i = 1 .. attempts-1. The final attempt is not followed by a sleep. Return the summed sleep time.
Your Task
Implement:
def total_backoff(base, cap, attempts):
Return the total seconds slept (float) across all inter-attempt waits.
Input Format
- base (float), cap (float), attempts (int).
Output Format
- A float (total sleep seconds).
Sample
print(total_backoff(1.0, 8.0, 4))
Output:
7.0
Example:
print(total_backoff(1.0, 8.0, 4))
7.0
- With
attempts = 4, the agent sleeps between attempts 1→2, 2→3, and 3→4, resulting in 3 total sleep intervals. - For the first interval (after attempt 1), the backoff is calculated as min(1.0×20,8.0)=min(1.0,8.0)=1.0 second.
- For the second interval (after attempt 2), the backoff doubles to min(1.0×21,8.0)=min(2.0,8.0)=2.0 seconds.
- For the third interval (after attempt 3), the backoff doubles again to min(1.0×22,8.0)=min(4.0,8.0)=4.0 seconds.
- Summing these individual sleep durations gives the total latency: 1.0+2.0+4.0=7.0.
- The final output is 7.0
Constraints:
attempts >= 1; with 1 attempt there are no sleeps (return 0.0).- Sleep after attempt
iismin(base * 2**(i-1), cap)fori in 1..attempts-1. - Return a float.
1. Background Knowledge
Exponential backoff is a standard reliability pattern used in distributed systems, API clients, and AI agent frameworks. When a transient failure occurs, the caller waits before retrying. The wait time grows exponentially (typically by a factor of 2) so that a burst of failures does not hammer the service. The i-th sleep is proportional to base⋅2i−1.
In production systems, unbounded exponential growth is dangerous: a single misconfigured loop could sleep for days. Therefore, a cap is applied: the actual sleep is min(base⋅2i−1,cap). Once the uncapped value exceeds the cap, every subsequent sleep equals the cap. This creates a piecewise sequence: a geometric prefix followed by a constant tail.
The problem asks for the total wall-clock delay, which is the sum of all inter-attempt sleeps. Note that with attempts total tries, there are only attempts - 1 sleeps (no sleep after the final attempt). If attempts <= 1, the total is zero.
2. Algorithm Approach
This is a prefix-sum with saturation problem. The sleep sequence has two regimes:
- Geometric phase: while base⋅2i−1<cap, the sleep is base⋅2i−1.
- Capped phase: once the value reaches or exceeds cap, every remaining sleep equals cap.
You can either iterate through all attempts - 1 sleeps and apply min() at each step, or compute the geometric prefix sum analytically and add the constant tail. For clarity and correctness, the iterative approach is preferred unless attempts is extremely large.
3. Step-by-Step Strategy
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.