Distributed deadlock detection

Abstract

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. Categories and Subject Descriptors: C. 2.4 [Computer-Communication Networks]: Distributed Systems--distributed applications; D. 4.1 [Operating Systems]: Process Management--deadlocks; synchronization; D. 4.4 [Operating Systems]: Communications Management--network communi-cation General Terms: Algorithms Additional Key Words and Phrases: Distributed deadlock detection, message communication systems, resource deadlock, communication deadlock