In the literature, only a few studies have been performed on the distributed deadlock detection and resolution problem in the generalized request model. Most of the studies are based on the diffusing computation technique where propagation of probes and backward propagation of replies are required to detect deadlock. The replies carry the dependency information between processes for the initiator of the algorithm to determine deadlock. Since fast detection of deadlock is critical, we take a centralized approach that removes the need of backward propagation of replies, but sends the dependency information directly to the initiator of the algorithm. This enables reduction of time cost for deadlock detection to half of that of the existing distributed algorithms. The algorithm is extended to handle concurrent executions in order to further improve deadlock detection time, whereas the current algorithms focus only on a single execution. Simulation experiments are performed to see the effectiveness of this centralized approach as compared to previous distributed algorithms. It is found that our algorithm shows better results in several performance metrics especially in deadlock latency and algorithm execution time.

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.

This paper presents a deadlock detection algorithm under the OR request model in distributed systems. The initiator of the algorithm constructs a reduced wait-for graph through propagation of probes and receiving replies directly from the processes involved in the execution. A scheme of encoding path information from the initiator to each process is developed so that blocking relationship between processes is deduced at the initiator rather than explicitly sent to the initiator. This helps reduce the amount of information carried by the reply messages. Time complexity is improved to d as compared to 2d in the current best algorithms, where d is the diameter of the wait-for graph. All deadlocks reachable from the initiator are resolved, whereas the current algorithms only know if the initiator is in deadlock. 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 existing algorithms ignore this issue and deal with single execution of the algorithm only.

The paper presents a probabilistic performance analysis of a deadlock detection algorithm in distributed systems. Although there has been extensive study on deadlock detection algorithms in distributed systems, little attention has been paid to the study of the performance of these algorithms. Most work on performance study has been achieved through simulation but not through an analytic model. Min (1990), to the best of our knowledge, made the sole attempt to evaluate the performance of distributed deadlock detection algorithms analytically. Being different from Min's, our analytic approach takes the time-dependent behavior of each process into consideration rather than simply taking the mean-value estimation. Furthermore, the relation among the times when deadlocked processes become blocked is studied, which enhances the accuracy of the analysis. We measure performance metrics such as duration of deadlock, the number of algorithm invocations, and the mean waiting time of a blocked process. It is shown that the analytic estimates are nearly consistent with simulation results.

This paper presents a distributed algorithm for detecting deadlocks in the OR request model in distributed systems. The initiator of the algorithm builds a reduced local wait-for graph to determine a deadlock by employing two phases for probe propagation and receiving replies. The proposed algorithm exhibits faster deadlock detection and shorter blocked time of processes than the current algorithms. Furthermore, the deadlock resolution is simplified without any additional message transmission.

We propose a distributed deadlock detection algorithm which detects cycles made of back edges in a distributed search tree. Our algorithm detects the deadlocks in which the initiator of the algorithm is directly or indirectly involved, while most of the proposed deadlock detection algorithms only detect the cycles in which the initiator is directly involved. Our algorithm is a reduced version of the one proposed previously, which resolves all deadlocks reachable from the initiator in a single execution by propagating the probe messages to the nodes in the search tree and having each node resolve deadlocks in its subtree with collected information on dependency between its subtree nodes. Our algorithm substantially reduces the message overhead of the previous algorithm. We compare the performance of our algorithm with others through extensive simulation. It is found that our algorithm detects deadlocks as fast as the previous algorithm with much fewer messages. The simulation results show that our algorithm outperforms other algorithms considerably in major performance measures.