A Distributed Algorithm for Generalized Deadlock Detection

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 to those of previously known distributed AND-OR deadlock detection algorithms