Retry with Capped Exponential Backoff and Jitter Cap
Problem Statement
Generate the backoff delay schedule for a retrying pipeline step: exponential growth, capped at a maximum, for a given number of retries.
Background
For retry attempt i (0-indexed), the base delay is base * (2 ** i), capped at cap. Return the list of delays for attempts 0 .. retries-1. This is the deterministic (pre-jitter) schedule used to reason about worst-case total wait.
Your Task
def backoff_schedule(base, cap, retries):
Return the list of capped delays.
Input Format
- base (number), cap (number), retries (int).
Output Format
- A list of numbers.
Sample
print(backoff_schedule(1, 10, 5))
Output:
[1, 2, 4, 8, 10]
Example:
print(backoff_schedule(1, 10, 5))
[1, 2, 4, 8, 10]
- Initialize the parameters from the input: base delay b=1, maximum cap c=10, and total retries n=5.
- For the first two attempts (i=0,1), calculate the exponential delay b⋅2i and compare it to the cap. Since 1⋅20=1 and 1⋅21=2 are both less than 10, the delays remain 1 and 2.
- For the next two attempts (i=2,3), the exponential growth continues: 1⋅22=4 and 1⋅23=8. Both values are still below the cap of 10, so the delays are 4 and 8.
- For the final attempt (i=4), the calculated exponential delay is 1⋅24=16. Because this exceeds the cap, the delay is constrained to the maximum value of 10.
- The final output is [1, 2, 4, 8, 10]
Constraints:
- delay[i] = min(base * 2**i, cap).
- Return
retriesentries (empty if retries == 0).
1. Background Knowledge
Exponential backoff is a standard retry strategy in distributed systems where the wait time between consecutive attempts grows exponentially. For attempt index i (0-indexed), the raw delay is computed as:
di=base×2iThis rapid growth prevents a failing downstream service from being hammered by a burst of retries, giving it time to recover. In production systems, jitter (randomization) is added to avoid the "thundering herd" problem, but this problem focuses on the deterministic, pre-jitter schedule.
A critical practical concern is resource exhaustion. Without a limit, 2i grows unboundedly, which could cause a single client to wait for hours or days. Therefore, a cap (maximum delay) is applied: the actual delay is min(base×2i,cap). Once the exponential value exceeds the cap, all subsequent delays remain constant at the cap value. This creates a piecewise function: exponential growth for early retries, then a flat plateau.
In ML pipelines, this pattern is essential for reliability. When a data ingestion step or model evaluation job fails transiently (e.g., due to a network timeout or a flaky GPU driver), the pipeline retries with increasing patience. The deterministic schedule allows engineers to calculate the worst-case total wait time for a given number of retries, which is crucial for SLA (Service Level Agreement) planning and cost estimation.
2. Algorithm Approach
The problem requires generating a sequence of length retries. The core logic is a simple iterative loop that computes each delay independently based on its index.
- Initialize an empty list to store the delays.
- Iterate from i=0 to i=retries−1.
- For each i, calculate the raw exponential delay: base×2i.
- Apply the cap: delay=min(raw_delay,cap).
- Append the result to the list.
- Return the list.
This is a direct translation of the mathematical definition into code. No complex data structures or advanced algorithms are needed; the challenge lies in correctly handling the indexing and the capping logic.
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.