Optimal deadlock detection in distributed systems based on locally constructed wait-for graphs

Shigang Chen, Yi Deng, Paul Attie, Wei Sun

Research output: Contribution to conferencePaperpeer-review

30 Scopus citations


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 - 2n + 2l, which is O(n2) 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 deadlock is readily available at the initiator process, rather than distributed among different processes, it significantly simplifies the task of deadlock resolution, and helps to reduce system overhead associated with the resolution. The time complexity of our algorithm is also better than or equal to the existing algorithms.

Original languageEnglish (US)
Number of pages7
StatePublished - Jan 1 1996
Externally publishedYes
EventProceedings of the 1996 16th International Conference on Distributed Computing Systems - Hong Kong, Hong Kong
Duration: May 27 1996May 30 1996


ConferenceProceedings of the 1996 16th International Conference on Distributed Computing Systems
CityHong Kong, Hong Kong

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this