Distributed deadlock detection
Distributed deadlock models are presented for resource and communication deadlocks. Simple distributed algorithms for detection of these deadlocks are given. We show that all true deadlocks are detected and that no false deadlocks are reported. In our algorithms, no process maintains global information; all messages have an identical short length. The algorithms can be applied in distributed database and other message communication systems.
© 1983 ACM. Received May 1981; revised August 1982; accepted November 1982. This work has been supported by the Air Force Office of Scientific Research under grant AFOSR 81-0205 and by the University of Texas under a grant from the University Research Institute. We are particularly grateful to E. W. Dijkstra and C. S. Scholten for their encouragement and advice. In particular, the proof of Theorem 2 was suggested by Scholten. We were helped greatly by comments from G. Andrews, N. Francez, C. A. R. Hoare, Anita Jones, and F. Schneider. Special thanks to the referees for their comments.