📘

Circuit Breaker State Machine for a Failing Tool

Problem Statement

When a downstream tool is genuinely down, retrying is worse than useless: every attempt costs a step, a timeout and a slot in the context window, and the agent's plan drifts further from reality with every empty observation. A circuit breaker stops the bleeding - after enough consecutive failures it opens and rejects calls without making them, then cautiously probes for recovery.

Background

Three states:

closed - calls go through. A failure increments a consecutive-failure counter; a success resets it to zero. When the counter reaches failure_threshold, the breaker opens and records opened_at = t of that event.
open - any event at time t < opened_at + cooldown is rejected: the call is not executed at all, and its t is recorded. The first event at t >= opened_at + cooldown transitions the breaker to half-open and is then processed by the half-open rules.
half-open - a trial window. Successes accumulate; on reaching half_open_successes the breaker closes and all counters reset. A single failure re-opens it immediately with opened_at = t of that failure.

The counters reset on every state change, so a fresh open always requires failure_threshold fresh consecutive failures.

Your Task

Implement:

def run_circuit_breaker(events, failure_threshold, cooldown, half_open_successes):

events: list of {"t": int, "result": "success"|"failure"}, already in ascending time order.

Return:

final_state: "closed", "open" or "half_open".
rejected: list of t values that were short-circuited, in event order.
transitions: list of strings "<from>-><to>@<t>", in the order they happened.

Input/Output Format

Returns a dict with those three keys. The breaker starts closed.

Sample

events = [{"t": 1, "result": "failure"}, {"t": 2, "result": "failure"},
          {"t": 3, "result": "failure"}, {"t": 4, "result": "success"}]
print(run_circuit_breaker(events, 2, 10, 1))
# {'final_state': 'open', 'rejected': [3, 4], 'transitions': ['closed->open@2']}

Two consecutive failures open the breaker at t=2; the cooldown runs to t=12, so both later events are rejected without ever being tried.

Example:

Input:

events = [{'t':1,'result':'failure'},{'t':2,'result':'failure'},{'t':3,'result':'failure'},{'t':4,'result':'success'}]
print(run_circuit_breaker(events, 2, 10, 1))

Output:

{'final_state': 'open', 'rejected': [3, 4], 'transitions': ['closed->open@2']}

Reasoning:

The failures at t=1 and t=2 are two consecutive failures, hitting the threshold of 2, so the breaker opens at t=2 with a cooldown to t=12. The events at t=3 and t=4 both fall inside the cooldown, so they are rejected without being executed - the success at t=4 never gets a chance to reset anything.

Constraints:

1 <= len(events) <= 1000; t values are non-decreasing ints
failure_threshold >= 1, cooldown >= 0, half_open_successes >= 1
A rejected event is never executed and never affects any counter
The probe event at t >= opened_at + cooldown is processed under half-open rules, not skipped
Every state change resets the failure and success counters
transitions uses the exact format "<from>-><to>@<t>"

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAHard Bootstrap Confidence Interval Width for Eval AccuracyMedium Route to the Cheapest Model Meeting QualityMedium pass@k EstimatorMedium Savings from a Semantic CacheMedium

1. Background Knowledge

The Circuit Breaker pattern is a fundamental resilience strategy in distributed systems and AI agent workflows. Its primary purpose is to prevent a system from repeatedly attempting to execute an operation that is likely to fail, thereby conserving resources (time, memory, API slots) and allowing the failing component time to recover. Without this mechanism, an agent might waste significant context window space and execution steps on timeouts or errors, causing the overall plan to drift or stall.

The pattern operates using a finite state machine with three distinct states: closed, open, and half-open. In the closed state, the system behaves normally, allowing requests to pass through while monitoring for failures. If the number of consecutive failures exceeds a defined failure_threshold, the breaker opens. In the open state, all requests are immediately rejected without being processed, effectively "short-circuiting" the call. This state persists for a defined cooldown period.

After the cooldown expires, the breaker transitions to half-open. This is a probing state where a limited number of requests are allowed through to test if the downstream service has recovered. If these probe requests succeed (reaching half_open_successes), the breaker closes again, resuming normal operation. If any probe fails, the breaker immediately re-opens, resetting the cooldown timer. This mechanism ensures that recovery is verified before full traffic is restored, preventing immediate re-failure.

2. Algorithm Approach

The core algorithmic pattern here is a Finite State Machine (FSM) simulation driven by a sequential event stream. You must maintain the current state of the breaker and several auxiliary variables (counters and timestamps) that evolve as each event is processed.

The approach involves iterating through the events list in chronological order. For each event, you check the current state and apply the specific transition rules:

Closed: Track consecutive failures. If the count hits the threshold, transition to Open.
Open: Check if the current time t is within the cooldown window. If so, reject the event. If the cooldown has passed, transition to Half-Open and process the event as if it were the first probe.
Half-Open: Track successes. If the success count hits the target, transition to Closed. If a failure occurs, transition back to Open.

Key to this approach is correctly handling the "edge" cases where a state transition occurs during the processing of an event. For instance, the event that causes the threshold to be met is the one that triggers the transition, and its result is still considered part of the logic that led to the new state.

3. Step-by-Step Strategy

Initialize State Variables:

Set state = "closed".
Initialize failure_count = 0 and success_count = 0.
Initialize opened_at = None (to track when the breaker last opened).
Initialize output lists: rejected = [] and transitions = [].

Iterate Through Events: Loop through each event e in events, extracting t = e["t"] and result = e["result"].
Handle "Closed" State:

If result is "success", reset failure_count = 0.
If result is "failure", increment failure_count.
Check if failure_count == failure_threshold. If true:
Record transition: f"closed->open@{t}".
Set state = "open".
Set opened_at = t.
Reset failure_count = 0 (as per "counters reset on every state change").

Handle "Open" State:

Check if t < opened_at + cooldown.
If true (still in cooldown):
Append t to rejected.
Do not process the result further; the call was never made.
If false (cooldown expired):
Record transition: f"open->half_open@{t}".
Set state = "half_open".
Crucial: Now process the current event e using the Half-Open rules (see below). Do not skip it.

Handle "Half-Open" State:

If result is "success":
Increment success_count.
Check if success_count == half_open_successes. If true:
Record transition: f"half_open->closed@{t}".
Set state = "closed".
Reset success_count = 0 and failure_count = 0.
If result is "failure":
Record transition: f"half_open->open@{t}".
Set state = "open".
Set opened_at = t.
Reset success_count = 0 and failure_count = 0.

Return Results: After the loop, return the dictionary with final_state, rejected, and transitions.

4. Common Pitfalls

Processing the Transition Event: In the Open state, when the cooldown expires, the event that triggers the transition to Half-Open must still be processed according to Half-Open rules. A common mistake is to record the transition and then continue to the next event, skipping the probe.
Counter Reset Timing: The problem states counters reset on every state change. Ensure you reset failure_count when moving from Closed to Open, and reset both counts when moving from Half-Open to Closed or Open. Failure to reset leads to incorrect thresholds being met prematurely.
Cooldown Boundary Condition: The condition is t < opened_at + cooldown for rejection. If t == opened_at + cooldown, the cooldown has expired, and the breaker should transition to Half-Open. Be careful with strict inequality vs. non-strict.
State Persistence: Remember that opened_at is only relevant when the state is Open. When transitioning to Half-Open or Closed, you don't need to track opened_at anymore until it opens again.
Multiple Transitions per Event: While rare, ensure your logic doesn't allow two transitions from a single event (e.g., Open -> Half-Open -> Closed in one step). The problem implies a single transition per event maximum. The Half-Open processing happens after the Open->Half-Open transition is recorded.

5. Time & Space Complexity

Time Complexity: $O(N)$ , where $N$ is the number of events. We iterate through the events list exactly once, performing constant-time checks and updates for each event.
Space Complexity: $O(N)$ in the worst case for the output lists. The rejected list can grow up to $N$ if all events are rejected. The transitions list is bounded by $N$ but typically much smaller. Auxiliary variables use $O(1)$ space.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.