Cycles in the wait-for graph, not liveness checks

Twelve minutes into run_9104 the platform has every reason to believe the run is fine. The liveness probe on each of the five agent workers — the endpoint the platform polls to ask whether a process is still up and answering — returns 200. The ledger shows four claimed tasks with valid leases, all renewed in the last ten seconds. Token usage across the run is 31,000 out of a 400,000 allowance. Every agent has emitted a status in the last thirty seconds. The run has produced no artifact since 11:04.

Here is what the monitoring stack actually has to work with:

{"agent": "extractor-2",  "state": "running", "healthy": true,
 "last_heartbeat": "11:16:41Z", "tokens_used": 8120,  "status": "waiting for input"}
{"agent": "reconciler",   "state": "running", "healthy": true,
 "last_heartbeat": "11:16:39Z", "tokens_used": 6440,  "status": "waiting for input"}
{"agent": "writer",       "state": "running", "healthy": true,
 "last_heartbeat": "11:16:44Z", "tokens_used": 2210,  "status": "waiting for input"}

Three agents saying the same true thing. One of them is waiting on an OCR job that will return in ninety seconds and then the run will finish normally. The other two are waiting on each other and will still be waiting at midnight. Nothing in those three records distinguishes the cases, and no amount of additional health signal will, because health is a property of a process and the failure is a property of a relation between processes. The probe can only ever answer whether a worker can respond, and all three can.

The field that turns a status into an edge#

The fix is to make each agent report the object of its wait alongside the fact of it. A blocked step emits a descriptor naming what would have to happen for the agent to proceed:

{
  "run_id": "run_9104",
  "agent": "reconciler",
  "step": 7,
  "at": "11:16:39Z",
  "blocked_on": {
    "kind": "artifact",
    "id": "clause_table:bundle_b7",
    "since": "11:04:58Z",
    "wait_deadline": "11:34:58Z"
  }
}

Three details in that record do work. kind says what class of thing is being waited for, because the resolution rule differs — an artifact resolves to whoever is producing it, a lock resolves to whoever holds it, a tool call resolves to nothing inside the run. since gives the age of the wait, which is what stops a momentary block from being treated the same as a twelve-minute one. wait_deadline bounds the wait independently of the run's overall deadline, so a legitimate wait is not open-ended.

Those descriptors assemble into a wait-for graph, which has one node per agent and an edge from A to B when A cannot proceed until B does something; a set of agents each waiting on the next, closing back on itself, is a cycle in that graph and is what a deadlock looks like as data. Turning descriptors into a graph needs one resolution step per edge. blocked_on.kind == "agent" is already an edge. kind == "artifact" becomes an edge to the agent that currently owns the ledger task producing that artifact, which the ownership fields from 11.12 make a direct lookup. kind == "lock" becomes an edge to the current lease holder. kind == "tool" or kind == "human" produces no edge at all, because the thing being waited on is outside the run and cannot be part of a cycle within it.

def build_wait_for(run_id, ledger, steps):
    """Edge A -> B means: A cannot proceed until B does something."""
    edges = {}
    for rec in steps.latest_per_agent(run_id):
        b = rec.get("blocked_on")
        if b is None:
            continue                       # agent is working, no edge
        if b["kind"] == "agent":
            target = b["id"]
        elif b["kind"] == "artifact":
            target = ledger.owner_of_task_producing(b["id"])
        elif b["kind"] == "lock":
            target = ledger.lease_holder(b["id"])
        else:
            target = None                  # tool / human: leaves the run
        if target and target != rec["agent"]:
            edges.setdefault(rec["agent"], set()).add(target)
    return edges

For run_9104 that produces three nodes with edges, one of which goes nowhere useful.

The reconciler and extractor-2 form a cycle of length two. The writer has an outgoing edge that terminates outside the run, which makes it a sink — a node whose edge leads out of the graph and never comes back — rather than part of a cycle, so the writer is waiting legitimately and will resume when OCR returns. The picture the on-call engineer assembled by hand in the previous chapter is now the output of a query.

Finding the cycle, and how cheap it is#

Cycle detection on a directed graph is a depth-first search with three-colour marking, and the whole detector is short enough to read in one sitting.

def find_cycle(edges):
    WHITE, GREY, BLACK = 0, 1, 2
    colour, stack = {}, []

    def visit(node):
        colour[node] = GREY
        stack.append(node)
        for nxt in edges.get(node, ()):
            if colour.get(nxt, WHITE) == GREY:          # back edge: cycle
                return stack[stack.index(nxt):] + [nxt]
            if colour.get(nxt, WHITE) == WHITE:
                found = visit(nxt)
                if found:
                    return found
        colour[node] = BLACK
        stack.pop()
        return None

    for node in list(edges):
        if colour.get(node, WHITE) == WHITE:
            found = visit(node)
            if found:
                return found
    return None

A run in this pipeline has at most a dozen agents, so the graph has at most a dozen nodes and the search finishes in well under a millisecond. Running it every fifteen seconds across 400 concurrently live runs is roughly 27 detector invocations per second on graphs of a dozen nodes, which is not a measurable load on anything. The expensive part is not the algorithm — it is having agents that report blocked_on at all, which is a change to every agent's step loop rather than a change to the monitoring stack.

Databases have been doing exactly this since the 1970s, and their design choices are worth borrowing rather than rediscovering. PostgreSQL does not run a deadlock check on every lock acquisition, because the check is pointless in the overwhelming majority of cases where the lock is granted immediately; instead a transaction that has been waiting for deadlock_timeout — one second by default — triggers a wait-for graph search, and only then does the server look for a cycle and abort one participant. The same shape works here: do not build the graph for every blocked step, build it for waits older than some threshold, which for agent runs with multi-minute tools is on the order of 60 to 120 seconds rather than one second. The other borrowing is the vocabulary. Coffman's four conditions for deadlock — mutual exclusion, hold-and-wait, no preemption, and circular wait — are a checklist for prevention as well as detection, and the cheapest one to break in an agent system is usually hold-and-wait, by requiring an agent to acquire everything it needs before starting rather than acquiring incrementally.

The descriptor has to come from the runtime, not the model#

The status: "waiting for input" line in the previous chapter's traces was generated by the model as part of its turn. That is fine for a human reading a trace and useless as the basis of a graph, because a model asked to name what it is blocked on will produce something plausible whether or not it is true. Ask an extractor for a blocked_on field and it will happily emit {"kind": "artifact", "id": "clause table from the other extractor"}, which is a sentence rather than a key. ledger.owner_of_task_producing returns None for it, the edge disappears, and a real two-cycle presents as two unconnected sinks — a false negative produced by the detector believing prose.

The descriptor has to be emitted by the code that performs the wait, where the identity of the thing being waited for is already a variable.

@asynccontextmanager
async def blocking_on(agent, kind, obj_id, timeout_s):
    agent.publish_step({"blocked_on": {"kind": kind, "id": obj_id,
                                       "since": now(),
                                       "wait_deadline": now() + timeout_s}})
    hb = asyncio.create_task(agent.heartbeat_while_blocked())
    try:
        yield
    finally:
        hb.cancel()
        agent.publish_step({"blocked_on": None})   # edge retracted on resume

async def await_artifact(agent, artifact_id, timeout_s=900):
    async with blocking_on(agent, "artifact", artifact_id, timeout_s):
        return await store.wait_for(artifact_id, timeout_s)

Every wait in the system goes through one of a handful of these wrappers — artifact, lock, queue receive, sub-agent result, human approval — and each wrapper knows the exact identifier the ledger uses, so the resolution step is a lookup rather than a guess. The blocked agent also keeps heartbeating from inside the wrapper — re-emitting its step record on a fixed interval so that its absence, rather than its silence, is what signals trouble — which is what makes an agent that is genuinely blocked distinguishable from one whose host died: the first reports an edge every fifteen seconds, the second reports nothing.

The cost of this discipline is that any wait somebody implements by hand, with a bare await or a polling loop over the ledger, is invisible to the detector. Auditing for that is mechanical — grep for awaits outside the wrappers — and it is worth doing once per release, because a single unwrapped wait in the reconciler is enough to hide every cycle that passes through it.

What the graph does not see#

A wait-for graph answers one question: is there a set of agents inside this run, each of which is waiting on the next, closing back on itself. Several stuck-looking runs are not that, and treating the detector as a general stuck-run alarm produces both silence where you expected noise and noise where you expected silence.

The loop from run_8817 produces an entirely empty graph, because a looping agent is never blocked — it is making calls, it is spending tokens, and it reports no blocked_on at any step. Whatever else the wait-for graph does, it will never fire on a livelock — a run whose agents keep taking steps and spending budget without getting any closer to finishing, which is the active counterpart to a deadlock's total stillness — and that is why the previous chapter insisted the two failures need separate instruments.

The crashed-holder row is the more dangerous one, because it looks close enough to a cycle to invite confusion. If extractor-2's host is terminated while it holds the page lock, the reconciler's edge points at an agent that no longer exists and never emits another record. There is no cycle, since a cycle requires the edge to come back, and the run is nonetheless permanently stuck. The mechanism that resolves it is the expiring lease from 11.12 rather than anything in this chapter: when the lease lapses, the lock is reclaimable, the edge disappears, and the reconciler proceeds. A detector that only looks for cycles will report run_9104 healthy in that scenario for as long as you let it.

Edges also go stale in the ordinary case. An agent that reported blocked_on at 11:16:39 and then acquired what it needed at 11:16:45 leaves a record behind, and a detector reading the last record per agent will happily assemble a cycle out of two waits that no longer exist. The way to prevent it is to make edges expire the same way leases do: an edge is valid only if the underlying record is younger than two heartbeat intervals, so an agent that has resumed stops asserting its edge simply by heartbeating without one. In practice that turns "did I see a cycle" into "did I see a cycle in two consecutive samples", which costs an extra fifteen seconds of detection latency and removes essentially all of the false positives.

There is one more thing the graph will not give you, which is what to do about the cycle once you have it. Databases abort the transaction that has done the least work, on the grounds that it is the cheapest to redo. Agent runs have the same choice — abort the agent with the fewest completed steps, or the one holding the fewest resources, or the one furthest from a checkpoint — and the choice interacts with the shared budget and with what happens to the descendants of whichever agent you kill. That is a later chapter's problem.

The whole detector rests on an assumption worth stating plainly: it assumes that agents which are stuck say so. Every edge exists because some agent volunteered that it was blocked, and the entire graph for a run can be empty for two quite different reasons — every agent is making progress, or nobody is left to report anything. A run where no agent is executing and no message is outstanding looks, to this detector and to every liveness probe in the stack, exactly like a run that has just finished. Deciding which of those it is turns out to be a harder question than finding cycles, and it is the subject of the next chapter.