Optimal Deadlock Detection in Distributed Systems Based on Locally Constructed Wait-for Graphs

We present a new algorithm for detecting generalized deadlocks in distributed systems. Our algorithm incrementally constructs and reduces a wait-for graph (WFG) at an initiator process. This WFG is then searched for deadlock. The proposed algorithm has two primary advantages: First, it avoids sending messages along the edges of the global wait-for graph (WFG), thereby achieving a worst-case message complexity of 2n, where n is the number of processes in the WFG. Since information must be obtained from every process reachable from the initiator, this is optimal to within a constant factor. All the existing algorithms for the same problem construct a distributed snapshot of the WFG. As this involves sending messages along the edges of the WFG, the best available message complexity among these algorithms is 4e \Gamma 2n + 2l, which is O(n 2 ) in the worst case, where e and l are the number of edges and leaves in the WFG, respectively. Second, since the information about a detected deadl..