A distributed algorithm for generalized deadlock detection

Abstract

An efficient distributed algorithm to detect deadlocks in distributed and dynamically changing systems is presented. In our model, processes can request any N available resources from a pool of size M. This is a generalization of the well-known AND-OR request model. The algorithm is incrementally derived and proven correct. Its communication, computational, and space complexity compares favorably with those of previously known distributed AND-OR deadlock detection algorithms.