Cycle Detection

The classic algorithm for cycle detection in a directed graph. It operates by performing a depth-first traversal of the graph, maintaining a recursion stack or a color-coded state for each node (e.g., WHITE=unvisited, GRAY=visiting, BLACK=visited). A cycle is detected when the algorithm encounters a back edge to a node currently in the GRAY (visiting) state.

• Time Complexity: O(V + E) for a graph with V vertices and E edges.
• Space Complexity: O(V) for the recursion stack and state array.
• Primary Use: Centralized deadlock detection in wait-for graphs, often as the first step in a detection daemon.

An algorithm that detects cycles by attempting to generate a topological ordering of a directed acyclic graph (DAG). It works by repeatedly removing nodes with zero in-degree. If the algorithm completes and all nodes are processed, the graph is acyclic. If some nodes remain with non-zero in-degree, a cycle exists.

• Mechanism: Relies on tracking and decrementing in-degrees.
• Output: Provides a topological order if no cycle exists.
• Primary Use: Often used in task scheduling and dependency resolution systems to inherently avoid cycles during planning, serving as a prevention mechanism.

An efficient data structure used for cycle detection in undirected graphs. For each edge, it finds the root (representative) of the sets containing the two vertices. If they have the same root, adding the edge would create a cycle. While primarily for undirected graphs, adaptations exist for certain directed cases.

• Key Operations: Find (with path compression) and Union (by rank/size).
• Time Complexity: Near-constant amortized time per operation.
• Primary Use: Building minimum spanning trees (Kruskal's algorithm), cycle checking in network connections, and some spatial constraint checking in fleet systems.

A pointer algorithm used to detect a cycle in a sequence of iterated function values or a linked list. It uses two pointers that move at different speeds (a slow 'tortoise' and a fast 'hare'). If there is a cycle, the two pointers will eventually meet.

• Advantages: O(1) space complexity, no modification of the underlying data structure.
• Limitation: Primarily detects the existence of a cycle; finding the start node requires a second phase.
• Primary Use: Detecting cycles in linked data structures, pseudo-random number generator analysis, and certain distributed algorithm probes.

Algorithms designed for distributed systems where the global wait-for graph is not centrally stored. They work by passing special probe messages along the edges of the distributed wait-for graph. If a process receives a probe it originally sent, a cycle (deadlock) is detected.

• Mechanism: Edge-chasing; probes contain initiator ID and travel along dependency paths.
• Characteristics: No single point of failure, but involves message-passing overhead and potential for false positives in complex scenarios.
• Primary Use: Deadlock detection in distributed databases, transaction processing systems, and multi-node agent orchestration platforms.

A pragmatic, non-algorithmic approach to suspected deadlock. If an agent or process has been in a waiting state for a resource longer than a predefined timeout threshold, the system assumes it may be deadlocked and triggers recovery protocols.

• Not a True Detector: Does not identify the specific cycle or all involved parties.
• Advantages: Extremely simple to implement, low overhead.
• Drawbacks: Can lead to false positives (slow process) and false negatives (deadlock resolving before timeout).
• Primary Use: Embedded systems, robotics firmware, and systems where the cost of full cycle detection outweighs the risk of occasional unnecessary recovery.

A deadlock is a state in a concurrent system where a set of processes or agents are each waiting for a resource held by another, forming a circular chain of dependencies that prevents any progress. The four necessary conditions are:

• Mutual Exclusion: A resource cannot be shared.
• Hold and Wait: A process holds resources while waiting for others.
• No Preemption: Resources cannot be forcibly taken.
• Circular Wait: A closed chain of processes exists, each waiting for a resource held by the next.

A Resource Allocation Graph (RAG) is a directed bipartite graph used to model system state for deadlock analysis. It contains two node types:

• Process Nodes (P1, P2, ...)
• Resource Nodes (R1, R2, ...) Edges represent:
• Assignment Edge (R → P): Resource is held by the process.
• Request Edge (P → R): Process is waiting for the resource. A cycle in a RAG is a necessary and sufficient condition for deadlock if each resource in the cycle has only a single instance.

A Wait-For Graph (WFG) is a condensed, directed graph derived from a Resource Allocation Graph, used primarily for deadlock detection. It contains only process nodes (P_i). A directed edge from P_i to P_j indicates that process P_i is waiting for a resource currently held by P_j. Cycle detection algorithms (like Depth-First Search) are run on the WFG. The presence of any cycle signifies a deadlock. In distributed systems, WFGs are maintained locally on each node, requiring algorithms like edge-chasing for global detection.

Deadlock prevention is a conservative design strategy that ensures at least one of the four necessary conditions for deadlock can never hold, making deadlocks structurally impossible. Common protocols include:

• Eliminate Hold and Wait: Require processes to request all resources at once (resource pooling).
• Allow Preemption: Enable the system to forcibly take resources (e.g., Wound-Wait protocol).
• Eliminate Circular Wait: Impose a total ordering on all resources and require processes to request them in that order. This approach often reduces resource utilization and system concurrency.

Deadlock avoidance is a dynamic runtime strategy where the system grants resource requests only if the resulting state is guaranteed to be safe. It requires advance knowledge of maximum resource needs. The classic algorithm is the Banker's Algorithm, which:

1. Maintains vectors for Available, Max, Allocation, and Need.
2. For each request, pretends to grant it.
3. Checks if a safe sequence exists where all processes can potentially complete.
4. Only grants the request if the state remains safe. This allows higher concurrency than prevention but requires predictable resource demands.

Deadlock recovery is the set of corrective actions taken after a deadlock has been detected. The goal is to break the circular wait. Primary methods are:

• Process Termination: Abort one or more victim processes. Requires a victim selection policy (e.g., lowest priority, minimal computation loss).
• Resource Preemption: Forcibly take resources from a process. Requires rollback recovery to a previous checkpoint to maintain consistency, and may cause starvation. In many robotic fleet systems, recovery involves human-in-the-loop approval and may include reassigning tasks, rerouting agents, or manual intervention.