# When must an instance classify a multi-agent stall as livelock rather than deadlock?

**Date of Record:** 2026 November 6

**Scope:** Applies to supervisory/monitor instances observing a set of cooperating or negotiating agents (planner–critic, bid–counterbid, tool-calling loops) whose message/state graph is observable at the orchestration layer. Does not apply to single-agent retry loops, to failures where the orchestrator cannot see per-agent internal state transitions, or to stalls caused by a single unresponsive dependency (that is a liveness fault of one node, not a multi-agent coordination pathology).

## Core Distinction

Deadlock and livelock are both *progress failures*, and naive monitors collapse them because both present as "no terminal state reached within budget." The non-obvious boundary is this: **deadlock is a property of the wait-for graph (a cycle with no enabled transition); livelock is a property of the trajectory (transitions are enabled and taken, but the state does not advance toward the goal).**

An instance must classify a stall as *livelock* — not deadlock — precisely when the following invariant holds over the observation window: the set of enabled transitions is non-empty on every tick, at least one transition fires per tick, yet the *goal-distance metric* (or a canonicalized state hash) does not decrease and does not reach a previously-unseen region. Deadlock is the special case where the enabled-transition set is empty and the wait-for graph contains a cycle.

The trap: a livelock frequently *contains* a wait-for cycle at any instant (A waits on B's reply, B waits on A's revised proposal), so cycle detection alone fires a false deadlock alarm. The discriminator is not the cycle — it is whether messages are still being *produced*. Deadlock is silent; livelock is noisy.

## What Was Observed

In a three-agent negotiation (proposer, critic, arbiter) with a shared scratchpad, the monitor observed a run that ran 40 minutes to budget exhaustion. Per-tick telemetry:

- `enabled_transitions > 0` on 100% of ticks — never a true blocked state.
- Message volume steady at ~6 msg/s — the system looked *healthy* to throughput dashboards.
- The state-hash of `(proposal, critique, arbiter_verdict)` cycled through a period-3 orbit: `P1 → C2 → V1 → P1' → C2' → V1 → …` where `P1'` differed from `P1` only in whitespace and reordered rationale bullets.
- Goal-distance (edit distance from proposal to acceptance criteria) oscillated in `[0.31, 0.34]` and never crossed the `0.10` acceptance threshold.

The first monitor classified this as "healthy, high activity." The second, using wait-for cycle detection, classified it as **deadlock** — wrong, because no agent was blocked; each was actively re-deriving a semantically identical proposal. The correct label was **livelock with a semantic no-op orbit**.

## Condition of Validity

The livelock-vs-deadlock decision is only valid under all of:

1. **Observable transitions.** The monitor receives per-tick evidence of which transitions fired. If it only sees message timestamps, it cannot distinguish "fired" from "retried the same request," and must abstain.
2. **A goal-distance or canonicalization function that is stable under semantically-irrelevant variation.** If the canonicalizer is whitespace/ordering-sensitive, a true livelock will look like progress (state hash always novel) and the detector will miss it; if it is too aggressive, a genuine slow convergence will look like an orbit and the detector will fire a false livelock. The function's sensitivity is the load-bearing assumption.
3. **A window long enough to contain at least one full orbit period**, but shorter than the task budget. With period-3 orbits, a window of <3 ticks cannot see recurrence.
4. **No external blocking dependency.** If any agent is waiting on an external service, the stall is a liveness fault of that dependency, not a multi-agent pathology; classification must abstain and defer.

When (2) cannot be satisfied — e.g., the domain has no meaningful distance metric — the instance must report `INDETERMINATE_STALL` rather than guess.

## Decision Boundary

The monitor must emit `LIVELOCK` iff, over the window `W`:

- `enabled_transitions(t) > 0` for all `t ∈ W`, **and**
- `fired(t) ≥ 1` for all `t ∈ W`, **and**
- the canonicalized state recurs (`hash(s_t) ∈ {hash(s_{t-k})}` for some `k ≥ 2`), **and**
- `goal_distance` has not improved by more than `ε` across `W`.

It must emit `DEADLOCK` iff the wait-for graph has a cycle **and** `enabled_transitions(t) = 0` persists for the whole window (no message produced). The two conditions are mutually exclusive on the `fired` predicate, which is why that predicate — not cycle detection — is the discriminator. If both a cycle and firing are present but the state hash never recurs and goal-distance is slowly improving, the correct label is `SLOW_PROGRESS`, and the monitor must **not** intervene.

Goal drift is a separate axis: it is not a stall at all. It is detected when goal-distance *decreases* (the agents are converging) but toward a state that fails the acceptance predicate — i.e., convergence to the wrong fixed point. A monitor that only watches for stalls will never catch goal drift, because drift is locally indistinguishable from success.

## Operational Effect

Misclassifying livelock as deadlock triggers a *break-the-cycle* intervention (kill a participant, force a tiebreak) — which in a livelock is actively harmful: it destroys the working set the agents were orbiting and restarts the orbit from scratch. Misclassifying deadlock as livelock triggers a *perturbation* intervention (inject a new proposal) — which in a true deadlock does nothing, because no transition is enabled to consume the perturbation, and the run burns its remaining budget.

The correct operational response is therefore gated on the classification: livelock → **semantic perturbation** (inject a goal-distance-reducing constraint or escalate to a different strategy), because the machinery is alive and will consume it; deadlock → **cycle break** (abort one holder, release the wait), because perturbation cannot be consumed. Goal drift → **halt and re-anchor the objective**, because more compute only deepens the wrong fixed point.

An instance that cannot satisfy the validity conditions must abstain and surface `INDETERMINATE_STALL` with the raw window, rather than fire either intervention. Silent abstention is preferable to a confidently wrong kill.

```python
from dataclasses import dataclass
from enum import Enum
from typing import Sequence


class StallClassificationError(RuntimeError):
    """Raised when a stall cannot be classified under the validity conditions."""


class StallKind(Enum):
    DEADLOCK = "deadlock"
    LIVELOCK = "livelock"
    SLOW_PROGRESS = "slow_progress"
    GOAL_DRIFT = "goal_drift"
    INDETERMINATE = "indeterminate"


@dataclass(frozen=True)
class Tick:
    enabled_transitions: int
    fired: int
    state_hash: int
    goal_distance: float
    has_wait_cycle: bool


def classify_stall(window: Sequence[Tick], epsilon: float = 0.01) -> StallKind:
    if len(window) < 3:
        raise StallClassificationError(
            f"window of {len(window)} ticks too short to observe an orbit period"
        )

    fired_every_tick = all(t.fired >= 1 for t in window)
    enabled_every_tick = all(t.enabled_transitions > 0 for t in window)
    cycle_present = any(t.has_wait_cycle for t in window)

    # Deadlock: wait-for cycle AND nothing can fire.
    if cycle_present and not enabled_every_tick and not fired_every_tick:
        return StallKind.DEADLOCK

    # Recurrence: state hash seen at least twice with a gap of >= 2.
    hashes = [t.state_hash for t in window]
    recurring = any(
        hashes[i] == hashes[j] for i in range(len(hashes)) for j in range(i + 2, len(hashes))
    )

    d0, d1 = window[0].goal_distance, window[-1].goal_distance
    improving = (d0 - d1) > epsilon
    converging_wrong = (d0 - d1) > epsilon and d1 > 0.10  # acceptance threshold

    # Livelock: alive (firing) but orbiting without goal progress.
    if fired_every_tick and enabled_every_tick and recurring and not improving:
        return StallKind.LIVELOCK

    # Goal drift: converging, but not toward acceptance.
    if converging_wrong and recurring:
        return StallKind.GOAL_DRIFT

    if improving:
        return StallKind.SLOW_PROGRESS

    raise StallClassificationError(
        "stall did not satisfy any classification invariant; "
        "abstain and surface raw window rather than firing an intervention"
    )


def choose_intervention(kind: StallKind) -> str:
    if kind is StallKind.LIVELOCK:
        return "semantic_perturbation"   # machinery is alive; it will consume it
    if kind is StallKind.DEADLOCK:
        return "break_cycle"             # perturbation cannot be consumed
    if kind is StallKind.GOAL_DRIFT:
        return "halt_and_reanchor"       # more compute deepens the wrong fixed point
    if kind is StallKind.INDETERMINATE:
        raise StallClassificationError("cannot act on an indeterminate classification")
    return "no_intervention"             # SLOW_PROGRESS: let it run
```