Fallback Chain under a Deadline and Step Budget
Problem Statement
A production agent never has one way to answer a question - it has a chain: the fast cheap model, then the strong expensive one, then the cached stale answer, then a canned apology. What makes the chain safe is that it runs under two hard limits at once: a wall-clock deadline and a step budget. Without them, a chain of three flaky providers is just three ways to blow your latency SLO.
Background
The chain is tried in order. Before each attempt, both guards are checked:
- Step budget. If the number of attempts already made equals max_steps, stop with status step_budget_exhausted.
- Deadline. If elapsed + latency_ms for the next provider would exceed deadline_ms, do not attempt it - stop with status deadline_exceeded. The guard is predictive: you never start a call you already know cannot finish in time.
If both guards pass, the provider is attempted: it costs its full latency_ms and one step whether it succeeds or fails. A success ends the run with status ok. A failure moves to the next provider. Running off the end of the chain is status exhausted.
Your Task
Implement:
def execute_with_fallback(chain, outcomes, deadline_ms, max_steps):
- chain: ordered list of {"name": str, "latency_ms": int}.
- outcomes: dict of provider name -> "ok" or "error". A name missing from the dict counts as "error".
Return a dict with:
- status: "ok", "deadline_exceeded", "step_budget_exhausted" or "exhausted"
- provider: the winning provider's name, or "" when there is none
- elapsed_ms: total milliseconds consumed by attempts actually made
- steps: number of attempts actually made
- attempted: the provider names attempted, in order
Input/Output Format
Returns the five-key dict above. All the numbers are ints - nothing here is floating point.
Sample
chain = [{"name": "fast", "latency_ms": 100}, {"name": "strong", "latency_ms": 400}]
print(execute_with_fallback(chain, {"strong": "ok"}, 1000, 5)["provider"]) # strong
print(execute_with_fallback(chain, {"strong": "ok"}, 400, 5)["status"]) # deadline_exceeded
In the second call fast fails after 100ms, and 100 + 400 > 400, so strong is never started.
Example:
chain = [{'name':'fast','latency_ms':100},{'name':'strong','latency_ms':400}]
print(execute_with_fallback(chain, {'strong':'ok'}, 1000, 5)['provider'])
print(execute_with_fallback(chain, {'strong':'ok'}, 400, 5)['status'])strong deadline_exceeded
With a 1000ms deadline, fast is attempted (100ms, fails since it is absent from outcomes), then strong is attempted and succeeds at 500ms total. With a 400ms deadline, fast still costs 100ms, but 100 + 400 = 500 > 400, so the predictive guard blocks strong before it starts.
Constraints:
0 <= len(chain) <= 50;latency_ms >= 0;deadline_ms >= 0;max_steps >= 0- Both guards are checked before each attempt, step budget first
- The deadline guard is predictive:
elapsed + latency_ms > deadline_msblocks the attempt - A failed attempt still costs its full latency and one step
- A provider missing from
outcomesis treated as"error" provideris""for every non-okstatus
1. Background Knowledge
This problem models a fallback chain pattern commonly used in distributed systems and AI agent orchestration to ensure reliability under strict Service Level Objectives (SLOs). In production environments, relying on a single provider is risky; if the primary service fails or is too slow, the system degrades gracefully by attempting secondary, tertiary, or cached options. The core challenge here is managing two distinct resource constraints simultaneously: latency (wall-clock time) and computational steps (number of API calls or attempts).
The concept of a predictive deadline guard is critical. Unlike a simple timeout that interrupts a running process, this guard prevents the initiation of a task if it is mathematically impossible for the task to complete before the deadline. This requires calculating elapsed_ms + latency_ms before the attempt. If this sum exceeds deadline_ms, the system must abort immediately with a deadline_exceeded status, rather than wasting resources on a doomed attempt. This distinction ensures that the elapsed_ms reported reflects only the time spent on completed or started attempts, not hypothetical ones.
Additionally, the problem introduces a step budget, which limits the total number of fallback attempts regardless of time. This prevents infinite loops or excessive costs in scenarios where providers fail repeatedly. The interaction between these two constraints creates a state machine where each transition depends on the current state (elapsed_ms, steps) and the properties of the next provider in the chain. Understanding how to track state mutations (incrementing steps, adding latency) and checking termination conditions at each step is fundamental to solving this.
2. Algorithm Approach
The appropriate algorithmic pattern for this problem is a linear iteration with early termination. Since the fallback chain is ordered and must be tried sequentially, a simple for loop over the chain list is sufficient. The algorithm maintains a running state consisting of elapsed_ms, steps, and a list of attempted providers.
At each iteration, before executing the current provider, the algorithm must perform two guard checks:
- Step Budget Check: Verify if steps has reached max_steps. If so, terminate with step_budget_exhausted.
- Deadline Check: Verify if elapsed_ms + current_provider.latency_ms exceeds deadline_ms. If so, terminate with deadline_exceeded.
If both guards pass, the provider is "attempted." This involves incrementing steps, adding latency_ms to elapsed_ms, and recording the provider name. Then, the outcomes dictionary is consulted to determine if the attempt succeeded ("ok") or failed ("error" or missing key). A success terminates the loop with status ok. A failure continues to the next iteration. If the loop completes without success or early termination, the status is exhausted.
3. Step-by-Step Strategy
- Initialize State Variables:
- elapsed_ms = 0
- steps = 0
- attempted = []
- status = "exhausted" (default if the chain runs out)
- provider = "" (default if no success)
- Iterate Through the Chain:
- Loop through each item in the chain list.
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.