Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 1983 | public
Journal Article

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.

Additional Information

© 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.

Additional details

August 19, 2023
October 20, 2023