Towards efficient algorithms for deadlock detection and resolution in distributed systems

A theoretical framework for wait-for systems is provided, and general characteristics of a correct algorithm for deadlock detection and resolution are presented. It is shown that the computational upper bounds (number of messages) for deadlock detection and resolution are both O(n/sup 3/) in the worst case when n transactions are involved. This result is better than previous ones, which often are even exponential. Two correct deadlock detection and resolution algorithms are described which both achieve these upper bounds. >