Retry with Capped Exponential Backoff and Jitter Cap

mediumPROPipelines, Reliability & CostSystems & InfrastructureML Systems & Infrastructure 1

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

Input

print(backoff_schedule(1, 10, 5))

Output

[1, 2, 4, 8, 10]

Reasoning

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 \cdot 2^i$ and compare it to the cap. Since $1 \cdot 2^0 = 1$ and $1 \cdot 2^1 = 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 \cdot 2^2 = 4$ and $1 \cdot 2^3 = 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 \cdot 2^4 = 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 retries entries (empty if retries == 0).

More from ML Systems & Infrastructure 1

Spot vs On-Demand Expected-Cost Decisionmedium Minimum-Cost Job Scheduling Across Priced Windowshard Deduplicate Retried Pipeline Runs by Idempotency Keymedium Critical Path Length of a Pipeline DAGmedium Pipeline Stages Ready to Runeasy

Concept primerPREVIEW

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:

d_i = \text{base} \times 2^i

This 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, $2^i$ 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(\text{base} \times 2^i, \text{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 = \text{retries} - 1$ .
For each $i$ , calculate the raw exponential delay: $\text{base} \times 2^i$ .
Apply the cap: $\text{delay} = \min(\text{raw\_delay}, \text{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

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results