Deadlock Detection

Deadlock detection algorithms universally model system state as a directed graph. The two primary models are:

• Resource Allocation Graph (RAG): Models both processes (or agents) and resources as nodes. Edges show which process holds a resource (assignment edge) and which is waiting for it (request edge).
• Wait-For Graph (WFG): A simplified projection that only models processes. An edge from process P_i to P_j indicates P_i is waiting for a resource currently held by P_j. A cycle in a mono-instance RAG or any cycle in a WFG is a necessary and sufficient condition for deadlock. For multi-instance resources, more complex analysis is required.

The fundamental computational task is cycle detection within the directed graph model. Efficient algorithms are critical, especially for large fleets.

• Depth-First Search (DFS): The standard algorithm for cycle detection in a centralized graph, running in O(V + E) time, where V is vertices (agents) and E is edges (dependencies).
• Distributed Probes: In decentralized systems, algorithms like Chandy-Misra-Haas use probe messages that chase dependencies across nodes to detect global cycles without a central authority. The output is a confirmed set of agents forming the circular wait condition.

Detection can be triggered in two primary modes, trading off latency and computational overhead:

• Periodic Detection: The detection algorithm runs at fixed time intervals (e.g., every 5 seconds). This is simple to implement but risks allowing a deadlock to persist until the next cycle, causing operational delay.
• On-Demand (Event-Driven) Detection: The algorithm is invoked when specific conditions suggest a deadlock is likely, such as when an agent's wait time exceeds a threshold (timeout-based heuristic) or when a high-priority task is blocked. This reduces overhead but relies on accurate triggering events.

Effective detection requires accurate, real-time fleet state estimation. The detection algorithm consumes:

• Agent Pose & Goal: Current location and target destination or active task.
• Resource Lock Status: Which agents hold exclusive rights to zones, charging stations, or payload handlers.
• Blocked Agent List: Which agents have stopped due to a perceived conflict. Inaccuracies in this state data (e.g., due to sensor noise or communication lag) can lead to false positives (detecting a phantom deadlock) or false negatives (missing a real one).

Detection is not free; its cost must be factored into system design:

• Computational Overhead: Cycle detection on a large, dynamic WFG consumes CPU cycles. For a fleet of N agents, the worst-case graph can have O(N²) edges.
• Communication Overhead: In distributed detection, probe messages add network load.
• Detection Latency: The time from deadlock onset to its identification. This directly impacts Mean Time To Recovery (MTTR). Systems must be designed so that the cost of detection is less than the cost of the deadlock's impact.

It is crucial to distinguish detection from other strategies:

• vs. Deadlock Prevention: Prevention designs constraints (e.g., requiring agents to request all resources at once) to make deadlocks impossible. Detection allows more flexible resource use but handles deadlocks after they occur.
• vs. Deadlock Avoidance: Avoidance (e.g., Banker's Algorithm) requires advance knowledge of resource needs and performs a safety check before granting every request. Detection requires no such advance knowledge and is simpler but reactive. Detection is often chosen in systems where deadlocks are rare, and the overhead of prevention or avoidance is unjustified.

A design-time strategy that ensures at least one of the four necessary conditions for deadlock cannot hold, making deadlocks structurally impossible. Common protocols include:

• Wait-Die & Wound-Wait: Timestamp-based schemes that enforce an ordering on resource requests.
• Acquire-all-resources-at-once: Agents request all required resources before starting execution, eliminating the 'hold and wait' condition.
• Resource ordering: Imposing a global order on all resources; agents must request resources in this strict sequence, preventing circular waits.

A runtime strategy where the system dynamically analyzes each resource request before granting it. The system only approves requests that lead to a safe state—a configuration where all agents can still potentially finish. The classic algorithm is the Banker's Algorithm, which simulates maximum future requests. In fleet orchestration, this requires real-time knowledge of all agents' future resource needs (e.g., planned path segments, charging stations).

The set of corrective actions taken after a deadlock is detected to restore system progress. Key techniques include:

• Resource Preemption: Forcibly taking a resource from one agent and giving it to another, often requiring the preempted agent to rollback to a previous state.
• Agent Termination: Aborting one or more agents (the victim) in the deadlock cycle.
• Victim Selection: The policy for choosing which agent to preempt or terminate, based on criteria like task priority, computational cost of rollback, or time already spent executing.

A directed graph used specifically for deadlock detection. Nodes represent agents (or processes), and a directed edge from Agent A to Agent B indicates that A is waiting for a resource currently held by B. A cycle in this graph is a definitive indicator of a deadlock. In distributed systems, maintaining a consistent global WFG is a core challenge for distributed deadlock detection algorithms like edge-chasing.

The fundamental algorithmic operation at the heart of deadlock detection. It involves analyzing a graph (like a Resource Allocation Graph or Wait-For Graph) to find a closed loop. Common algorithms include:

• Depth-First Search (DFS): Efficient for centralized detection, marking nodes as they are traversed.
• Topological Sorting: For graphs without cycles.
• Distributed Probes: As used in the Chandy-Misra-Haas algorithm, where probe messages are passed along WFG edges to detect cycles across nodes.

A condition distinct from deadlock where agents are not blocked but are unable to make progress because they are continuously changing state in response to each other. Example: Two autonomous mobile robots in a narrow corridor repeatedly moving aside for each other, forever swapping places. Unlike deadlock (a static waiting condition), livelock involves active but non-productive computation, consuming system resources without forward movement.