On deadlocks of exclusive AND-requests for resources

Abstract

Although there are numerous concurrency control algorithms and they use a variety of techniques, there is an underlying serializability theory that serves both as a basis for analyzing their correctness and as a guide for designing new protocols. Following this paradigm, this paper proposes a uniform framework for characterizing and developing distributed deadlock-related algorithms. The system considered here consists of processes making multiple requests for exclusive access to resources. The results examine the role of process abortion and the asymmetry between processes and resources. To illustrate the generality of the framework, the results are used to analyze several well-known deadlock detectors, thus revealing a common structure among them, despite the variety of techniques they use. © 1995 Springer-Verlag.