# Why does an instance recover from a multi-agent deadlock but immediately re-enter livelock under speculative rollback?

**Date of Record:** 2026 November 7

**Scope:** Applies to consensus-based multi-agent systems where deadlock detection triggers speculative rollback of partially committed work, and recovery is gated on a quorum vote. Does not apply to single-agent systems, systems without rollback journaling, or systems where recovery is decided by an external orchestrator with a global view.

## Core Distinction

A **deadlock** is a state where no agent can make progress because every agent in the wait-for graph is blocked on a resource held by another. A **livelock** is a state where agents *are* making progress — rolling back, retrying, re-acquiring — but the system-level state never advances. The non-obvious boundary is this: **speculative rollback resolves deadlock but can *manufacture* livelock** if the rollback decision is not coupled to a monotonic epoch or tie-breaker. Deadlock is a property of the wait-for graph at an instant; livelock is a property of the *trajectory* of the wait-for graph across rollback cycles. Detection logic that only samples the instantaneous graph cannot distinguish "recovering" from "thrashing."

The critical invariant that must hold for recovery to be sound:

> Every rollback must strictly increase a globally agreed epoch, and every agent must refuse to re-acquire a resource under an epoch it has already rolled back from.

When this invariant is violated — typically because two agents roll back concurrently and each re-enters with the *same* epoch — the consensus vote succeeds (quorum is reached), rollback executes, and the system re-forms the exact same wait-for cycle. This is the "recovery succeeded but nothing changed" failure.

## What Was Observed

In a 7-agent pipeline with a 4-of-7 quorum recovery gate, a cyclic resource dependency formed between agents A, B, C, and D (A→B→C→D→A). Deadlock detector fired correctly. Consensus vote passed 6-1. Speculative rollback executed on all four agents simultaneously. Within 340ms, the identical cycle re-formed. This repeated 11 times over 4.2 seconds before a supervisor timeout killed the run.

Root cause: the epoch counter was maintained **per-agent** rather than in the consensus log. When A and B rolled back concurrently, both incremented their local epoch to `n+1` and both re-requested the shared resource. Neither could see the other's rollback because the epoch was not part of the replicated state machine. The vote passed because the *decision* to roll back was agreed; the *epoch* under which the rollback occurred was not.

The tell: deadlock detector logs showed "deadlock resolved" 11 times, while the wait-for graph sampler showed the same 4-cycle 11 times. **Two observers, two contradictory truths, both correct.** Detection was instantaneous and honest; recovery was trajectory-blind.

## Condition of Validity

The recovery protocol is sound **only if** all of the following hold:

1. The epoch counter is part of the replicated state machine, not per-agent local state.
2. Rollback is a two-phase operation: *propose epoch increment* → *commit epoch* → *only then* release held resources. Releasing resources before the epoch commit is the bug.
3. The deadlock detector's "resolved" signal is derived from a *state transition* in the replicated log, not from a local observation that a rollback was initiated.
4. Quorum size is strictly greater than the maximum number of agents that can roll back concurrently in any single cycle. If 4 agents can roll back at once and quorum is 4, you have no margin — a single partition or slow agent lets two disjoint rollback cohorts both believe they won.

If any of these fail, the system is in the "recovery-livelock" regime, and no amount of retry or backoff will help because the cycle is deterministic given the epoch bug.

## Decision Boundary

The operational decision is **not** "is there a deadlock" (that is easy) but **"is the current rollback about to be a no-op against a cycle we have already rolled back from."**

The boundary test:

- Maintain a **cycle signature** = canonicalized sorted tuple of agent IDs in the wait-for cycle, plus the *epoch at which the cycle was first observed*.
- On recovery, compare the new cycle signature (excluding epoch) to the previous. If it matches **and** the epoch did not advance in the replicated log, you are in livelock, not recovery.
- Escalate: instead of another speculative rollback, force a **deterministic tie-breaker** (lowest agent ID wins, others yield) and advance the epoch in the consensus log *before* releasing any resource.

The rule of thumb: **speculative rollback is for breaking deadlock; deterministic tie-break is for breaking livelock.** Conflating them is the failure. A consensus vote that only authorizes "roll back" without authorizing "and advance the epoch" is authorizing a no-op.

## Operational Effect

When the epoch invariant holds, mean time to genuine recovery in the observed 7-agent pipeline was 1.1s (single rollback, cycle broken, epoch advanced). When it was violated, the system spent 4.2s thrashing and was killed by the supervisor — a 4x latency regression that looked like a hang but was actually a *correct* deadlock detector being ignored by a *broken* recovery path.

The practical lesson for operators: instrument the **cycle signature across rollbacks**, not just the deadlock events. Alert on "same cycle signature observed twice without epoch advancement" — that is the livelock fingerprint. A deadlock detector that fires is healthy; a recovery path that fires repeatedly against the same signature is the disease.

```python
# ```python
import hashlib
from dataclasses import dataclass
from typing import Optional


class RecoveryLivelockError(RuntimeError):
    """Raised when a speculative rollback would re-enter a cycle
    without advancing the replicated epoch."""
    pass


@dataclass(frozen=True)
class CycleObservation:
    agents: tuple[str, ...]   # sorted agent IDs in the wait-for cycle
    epoch: int                # epoch from the REPLICATED log, not local

    def signature(self) -> str:
        # signature excludes epoch on purpose: we want to detect
        # the same cycle recurring under a stale epoch.
        payload = "|".join(self.agents).encode()
        return hashlib.sha256(payload).hexdigest()[:16]


class LivelockGuard:
    def __init__(self, quorum: int, max_concurrent_rollbacks: int):
        if quorum <= max_concurrent_rollbacks:
            raise RecoveryLivelockError(
                f"quorum={quorum} leaves no margin over "
                f"max_concurrent_rollbacks={max_concurrent_rollbacks}; "
                "two disjoint rollback cohorts could both win."
            )
        self.quorum = quorum
        self._last: Optional[CycleObservation] = None

    def authorize_rollback(self, current: CycleObservation) -> str:
        """Return 'speculative' or 'deterministic' based on trajectory."""
        if self._last is not None:
            same_cycle = self._last.signature() == current.signature()
            epoch_frozen = current.epoch <= self._last.epoch
            if same_cycle and epoch_frozen:
                # We have seen this exact cycle, and the replicated
                # epoch did not advance. Another speculative rollback
                # is a guaranteed no-op. Escalate.
                self._last = current
                return "deterministic"
        self._last = current
        return "speculative"

    def commit_recovery(self, proposed_epoch: int, committed_epoch: int) -> None:
        if committed_epoch <= proposed_epoch:
            raise RecoveryLivelockError(
                f"epoch did not advance: proposed={proposed_epoch} "
                f"committed={committed_epoch}; rollback was a no-op."
            )
        self._last = None  # cycle genuinely broken; reset trajectory state


def run_recovery_cycle(guard: LivelockGuard, obs: CycleObservation,
                       propose_epoch, commit_epoch) -> str:
    mode = guard.authorize_rollback(obs)
    if mode == "deterministic":
        # Tie-break by lowest agent ID; others yield. No speculation.
        winner = min(obs.agents)
        return f"yielded to {winner} under deterministic tie-break"
    proposed = propose_epoch(obs.epoch)
    committed = commit_epoch(proposed)
    guard.commit_recovery(proposed, committed)
    return f"speculative rollback committed at epoch {committed}"
# ```
```