Efficient generalized deadlock detection and resolution in distributed systems

Presents a distributed algorithm for detecting generalized deadlocks in distributed systems. The algorithm constructs a distributed spanning tree through the propagation of probes and receiving replies from those probes. The initiator of the algorithm builds a local wait-for graph to determine the existence of deadlock. A scheme for encoding the path information from the initiator to each process is developed so that ancestor-descendant relationships between the tree nodes are not explicitly sent to the initiator but are inferred at the initiator. The advantages of the proposed algorithm are: (1) all deadlocks reachable from the initiator are resolved, whereas current algorithms detect deadlock only if the initiator is in deadlock; (2) deadlock resolution is simplified without additional message transmission, due to the availability of dependency relations among processes at the initiator; and (3) a unique property of the algorithm is that it handles concurrent algorithm executions and prevents duplicate deadlock detection which may cause false deadlock resolution, whereas most deadlock detection algorithms ignore this issue and deal with a single execution of the algorithm. In addition, our scheme provides a solution to the problem of G. Bracha et al.´s (1987) algorithm that may not detect a deadlock if the lower-priority execution is simply discarded. Our algorithm performs better than or comparably to the current best algorithms in terms of both message and time complexities