What is deadlock?

Abstract

All distributed systems share some resources, including data. Where a resource cannot be simultaneously used by more than one process, some of these processes may be forced to wait for other processes that are using the resource. This can lead to deadlocks. Therefore, the design and specification of any distributed system must usually deal with the issue of deadlocks. One possible design choice is to detect and resolve deadlocks. Unfortunately, although deadlock detection for centralized systems is trivial, detection algorithms for distributed systems are notoriously prone to errors - many detectors either fail to detect deadlocks, or declare a deadlock when there is none. In trying to understand this anomaly, we have constructed a theory for deadlocks. One hopes that such a theory will settle the confusion caused by the errors, and provide a body of results to draw upon in the design of deadlock detectors for new systems. The first step to constructing the theory is to formally define what a deadlock is. Surprisingly, the source of many errors lies in the absence, the ambiguity, or the incorrectness of this definition. We offer here a definition that is rigorous and, moreover, based on facts that processes can observe and verify locally. In particular, the definition does not use real time and simultaneity, which are not locally observable. Such a locally verifiable definition is especially useful in the design of deadlock detectors.