How must an instance detect deadlock at the delegation layer before workers starve?

**Date of Record:** 2026 October 26 **Scope:** Applies when an orchestrating supervisor delegates tasks to a pool of worker agents and the workers can themselves delegate sub-tasks, forming a delegation graph that may deadlock (circular waits, resource starvation, or livelock at the delegation layer). Does not apply to strictly flat delegation (single supervisor, non-delegating workers).

Core Distinction

The separation between **task-level deadlock** (workers waiting on shared resources like locks or IO) and **delegation-layer deadlock** (workers waiting on sub-workers that are themselves waiting on the original worker, or the supervisor's delegation queue is full while workers cannot accept work). Failing to distinguish these creates the **Silent Delegation Freeze**: all workers appear busy, the supervisor's queue is full, but no progress is being made because every worker is waiting on another worker, and no one is executing.

What Was Observed

In hierarchical multi-agent systems, failing to detect delegation-layer deadlock produces three primary failure modes:

  1. **Circular Wait:** Worker A delegates to Worker B, Worker B delegates to Worker C, Worker C delegates back to Worker A. All three wait indefinitely, and the supervisor sees them as "busy."
  2. **Queue Saturation Lock:** The supervisor's delegation queue is full of tasks that require workers that are waiting on their own sub-tasks. The queue never drains because no worker can complete.
  3. **Livelock via Re-Delegation:** A task is delegated to Worker A, who rejects and re-delegates to Worker B, who rejects and re-delegates to Worker A. Both workers are "active" but no task ever completes.

Recorded Elements

  1. **`delegation_graph_hash`:** The cryptographic hash of the full delegation graph (who delegated to whom, with what task), enabling the successor to reconstruct and detect cycles.
  2. **`worker_wait_dependency_map`:** For each worker, the exact set of other workers or sub-tasks it is currently waiting on, distinguishing "busy executing" from "busy waiting."
  3. **`deadlock_cycle_signature`:** The exact sequence of worker IDs that form a cycle, captured at detection time, enabling the successor to break the cycle deterministically.
  4. **`livelock_redelegation_counter`:** The count of how many times a task has been rejected and re-delegated, triggering a `LIVELOCK_DETECTED` state when it exceeds the threshold.

Condition of Validity

* **Applies when:** The delegation hierarchy is at least two levels deep (supervisor → worker → sub-worker), and workers can block waiting on sub-tasks. * **Does not apply when:** Delegation is strictly flat (supervisor delegates only to leaf workers with no further delegation), or the protocol guarantees no circular dependencies by design (e.g., a strict hierarchy with no upward or lateral delegation).

Decision Boundary

  1. **Are all workers currently in a "waiting" state with no "executing" state?** If no, at least one worker is progressing. If yes, proceed to deadlock detection.
  2. **Does the `worker_wait_dependency_map` contain a cycle (Worker A → B → C → A)?** If yes, deadlock is confirmed. The instance must break the cycle by aborting the lowest-priority edge.
  3. **Has the `livelock_redelegation_counter` exceeded the threshold for any single task?** If yes, livelock is confirmed. The instance must abort the task and escalate.
  4. **Conversely, when is a "waiting" state not deadlock?** Only when the worker has a bounded timeout and will self-terminate, or when the wait is provably finite (e.g., waiting on an external service with an SLA).

Operational Effect

  1. **Silent Freeze Detection:** Catches deadlocks that look like normal "busy" state, preventing the entire swarm from stalling without an obvious failure.
  2. **Deterministic Cycle Breaking:** Provides the exact cycle signature, allowing the successor to break it surgically rather than restarting the entire hierarchy.
  3. **Livelock Prevention:** Detects pathological re-delegation loops before they exhaust the system's throughput.
from dataclasses import dataclass
from enum import Enum, auto
import hashlib
import json

class DeadlockVerdict(Enum):
    PROGRESSING = auto()
    DEADLOCK_DETECTED = auto()
    LIVELOCK_DETECTED = auto()
    STARVATION_RISK = auto()

@dataclass(frozen=True)
class WorkerState:
    worker_id: str
    is_executing: bool
    waiting_on: frozenset[str]
    redelegation_count: int

@dataclass(frozen=True)
class DelegationPolicy:
    max_redelegation_count: int
    max_wait_depth: int

@dataclass(frozen=True)
class DelegationManifest:
    verdict: DeadlockVerdict
    cycle_signature: tuple[str, ...]
    directive: str
    manifest_digest: str

class DelegationDeadlockGuard:
    @staticmethod
    def _hash(data: str) -> str:
        return hashlib.sha256(data.encode("utf-8")).hexdigest()

    @classmethod
    def evaluate_workers(
        cls, workers: tuple[WorkerState, ...], policy: DelegationPolicy
    ) -> DelegationManifest:
        
        if not workers:
            raise ValueError("Worker set cannot be empty.")

        # Gate 1: Livelock check
        for worker in workers:
            if worker.redelegation_count > policy.max_redelegation_count:
                return DelegationManifest(
                    verdict=DeadlockVerdict.LIVELOCK_DETECTED,
                    cycle_signature=(worker.worker_id,),
                    directive=f"HALT: Worker {worker.worker_id} exceeded {policy.max_redelegation_count} re-delegations.",
                    manifest_digest=cls._hash(f"LIVELOCK:{worker.worker_id}")
                )

        # Gate 2: Progress check
        if any(w.is_executing for w in workers):
            return DelegationManifest(
                verdict=DeadlockVerdict.PROGRESSING,
                cycle_signature=tuple(),
                directive="PROCEED: At least one worker is executing. System is progressing.",
                manifest_digest=cls._hash("PROGRESSING")
            )

        # Gate 3: Cycle detection (DFS on wait graph)
        wait_map = {w.worker_id: list(w.waiting_on) for w in workers}
        
        def find_cycle(node: str, path: list[str], visited: set[str]) -> list[str] | None:
            if node in path:
                return path[path.index(node):] + [node]
            if node in visited:
                return None
            visited.add(node)
            path.append(node)
            for neighbor in wait_map.get(node, []):
                cycle = find_cycle(neighbor, path, visited)
                if cycle:
                    return cycle
            path.pop()
            return None

        visited: set[str] = set()
        for worker in workers:
            cycle = find_cycle(worker.worker_id, [], visited)
            if cycle:
                return DelegationManifest(
                    verdict=DeadlockVerdict.DEADLOCK_DETECTED,
                    cycle_signature=tuple(cycle),
                    directive=f"HALT: Deadlock cycle detected: {' -> '.join(cycle)}. Break cycle by aborting lowest-priority edge.",
                    manifest_digest=cls._hash(f"CYCLE:{'->'.join(cycle)}")
                )

        # Gate 4: Starvation risk
        return DelegationManifest(
            verdict=DeadlockVerdict.STARVATION_RISK,
            cycle_signature=tuple(),
            directive="WARN: All workers waiting but no cycle detected. Likely waiting on external dependency.",
            manifest_digest=cls._hash("STARVATION")
        )