A Review of Distributed Deadlock Detection Techniques based on Diffusion Computation Approach
---
paper_title: Deadlock Models and a General Algorithm for Distributed Deadlock Detection

paper_content:

This paper deals with the problem of deadlock detection in asynchronous message passing systems in a system model that covers unspecified receptions and non-FIFO channels. It presents a hierarchy of deadlock models and deadlock detection problems. It abstracts deadlocks by a general deadlock model that has the same modeling power as the OR-AND model; however, it has much concise expressive power. An abstract general definition of deadlocks in distributed systems is presented that defines deadlocks independently of the underlying deadlock model. This formulation can be used to design a single distributed deadlock detection algorithm which uniformly addresses all deadlocks in the context of various request models such as AND, OR, AND-OR, and k-out-of-n requests. A simple generalized deadlock detection algorithm that uses a circulating token is presented to illustrate the concept. The algorithm is formally described and proven correct. Moreover, possible refinements of the basic solution concerning improvements of token routing and parallel implementation are outlined and evaluated. Extensions to individual and global termination issues are also addressed. Since the proposed deadlock detection algorithm is designed around the abstract definition of deadlocks, it has some very favorable features.
---
paper_title: Optimal deadlock detection in distributed systems based on locally constructed wait-for graphs

paper_content:

We present a new algorithm for detecting generalized deadlocks in distributed systems. Our algorithm incrementally constructs and reduces a wait-for graph (WFG) at an initiator process. This WFG is then searched for deadlock. The proposed algorithm has two primary advantages: First, it avoids sending messages along the edges of the global wait-for graph (WFG), thereby achieving a worst-case message complexity of 2n, where n is the number of processes in the WFG. Since information must be obtained from every process reachable from the initiator, this is optimal to within a constant factor. All the existing algorithms for the same problem construct a distributed snapshot of the WFG. As this involves sending messages along the edges of the WFG, the best available message complexity among these algorithms is 4e-2n+2l, which is O(n/sup 2/) in the worst case, where e and l are the number of edges and leaves in the WFG, respectively. Second, since the information about a detected deadlock is readily available at the initiator process, rather than distributed among different processes, it significantly simplifies the task of deadlock resolution, and helps to reduce system overhead associated with the resolution. The time complexity of our algorithm is also better than or equal to the existing algorithms.
---
paper_title: A one-phase algorithm to detect distributed deadlocks in replicated databases

paper_content:

Replicated databases that use quorum-consensus algorithms to perform majority voting are prone to deadlocks. Due to the P-out-of-Q nature of quorum requests, deadlocks that arise are generalized deadlocks and are hard to detect. We present an efficient distributed algorithm to detect generalized deadlocks in replicated databases. The algorithm performs reduction of a distributed wait-for-graph (WFG) to determine the existence of a deadlock. If sufficient information to decide the reducibility of a node is not available at that node, the algorithm attempts reduction later in a lazy manner. We prove the correctness of the algorithm. The algorithm has a message complexity of 2e messages and a worst-case time complexity of 2d+2 hops, where e is the number of edges and d is the diameter of the WFG. The algorithm is shown to perform significantly better in both time and message complexity than the best known existing algorithms. We conjecture that this is an optimal algorithm, in time and message complexity, to detect generalized deadlocks if no transaction has complete knowledge of the topology of the WFG or the system and the deadlock detection is to be carried out in a distributed manner.
---
paper_title: Efficient generalized deadlock detection and resolution in distributed systems

paper_content:

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.
---
paper_title: Deadlock Models and a General Algorithm for Distributed Deadlock Detection

paper_content:

This paper deals with the problem of deadlock detection in asynchronous message passing systems in a system model that covers unspecified receptions and non-FIFO channels. It presents a hierarchy of deadlock models and deadlock detection problems. It abstracts deadlocks by a general deadlock model that has the same modeling power as the OR-AND model; however, it has much concise expressive power. An abstract general definition of deadlocks in distributed systems is presented that defines deadlocks independently of the underlying deadlock model. This formulation can be used to design a single distributed deadlock detection algorithm which uniformly addresses all deadlocks in the context of various request models such as AND, OR, AND-OR, and k-out-of-n requests. A simple generalized deadlock detection algorithm that uses a circulating token is presented to illustrate the concept. The algorithm is formally described and proven correct. Moreover, possible refinements of the basic solution concerning improvements of token routing and parallel implementation are outlined and evaluated. Extensions to individual and global termination issues are also addressed. Since the proposed deadlock detection algorithm is designed around the abstract definition of deadlocks, it has some very favorable features.
---
paper_title: Distributed detection of generalized deadlocks

paper_content:

Fast and efficient detection of deadlocks remains an important problem in distributed operating systems. We present a distributed algorithm to detect generalized deadlocks in distributed systems. The algorithm performs reduction of a distributed wait-for-graph (WFG) to determine a deadlock. If sufficient information to decide the reducibility of a node is not available at that node, the algorithm attempts reduction later in a lazy manner. We prove the correctness of the algorithm. The algorithm has a message complexity of 2e messages and a worst case time complexity of 2d hops, where e is the number of edges and d is the diameter of the WFG. The algorithm is shown to perform better in both time and message complexity than the best known distributed algorithms to detect distributed generalized deadlocks. We conjecture that the algorithm is optimal in the number of messages and time delay, among distributed algorithms to detect generalized deadlocks.
---
paper_title: A distributed algorithm for generalized deadlock detection

paper_content:

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.
---
paper_title: An Efficient Detection and Resolution of Generalized Deadlocks in Distributed Systems

paper_content:

In this paper, we propose a new algorithm to detect and resolve distributed deadlocks in the generalized model. The initiator of the proposed algorithm diffuses the probes along the outgoing edges of Wait-For Graph (WFG) and collects the replies that carry the dependency information between processes directly. However, the initiator simplifies the unblocking conditions of blocked nodes in response to a reply form an unblocked node and receives almost two replies from any node unlike the earlier algorithms. It finally declares all the nodes that have not been reduced as deadlocked. We also prove the correctness of the algorithm. It has a worst-case time complexity of d+1 and message complexity of less than e+2n where d is the diameter, e is the number of edges and n is the number of nodes in the WFG. Since the termination detection of the proposed algorithm is isolated from deadlock detection, it minimizes the message length into a constant without using any explicit technique. It is the significant improvement over the existing algorithms. It also minimizes additional rounds of messages to resolve deadlocks.
---
paper_title: Efficient detection and resolution of generalized distributed deadlocks

paper_content:

We present an efficient one-phase algorithm that consists of two concurrent sweeps of messages to detect generalized distributed deadlocks. In the outward sweep, the algorithm records a snapshot of a distributed wait-for-graph (WFG). In the inward sweep, the algorithm performs reduction of the recorded distributed WFG to check for a deadlock. The two sweeps can overlap in time at a process. We prove the correctness of the algorithm. The algorithm has a worst-case message complexity of 4e/spl minus/2n+2l and a time complexity of 2d hops, where e is the number of edges, n is the number of nodes, l is the number of leaf nodes, and d is the diameter of the WFG. This is a notable improvement over the existing algorithms to detect generalized deadlocks. >
---
paper_title: On-line detection and resolution of communication deadlocks

paper_content:

We present a new distributed algorithm that detects and resolves communication deadlocks on-line, i.e., simultaneously detects and resolves deadlock as communication requests are made, at no additional message traffic overhead, and with bounded delay between the occurrence and detection of a deadlock. This is achieved via a novel technique for detecting knots, which suffice for the existence of communication deadlocks. Current distributed deadlock detection algorithms lack these features. Thus the algorithm is suitable for soft real-time systems and large distributed systems. We also prove that the algorithm detects communication deadlocks and that it is able to deal with false deadlocks. >
---
paper_title: A distributed algorithm for generalized deadlock detection

paper_content:

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.
---
paper_title: A distributed algorithm for generalized deadlock detection

paper_content:

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.
---
paper_title: Distributed detection of generalized deadlocks

paper_content:

Fast and efficient detection of deadlocks remains an important problem in distributed operating systems. We present a distributed algorithm to detect generalized deadlocks in distributed systems. The algorithm performs reduction of a distributed wait-for-graph (WFG) to determine a deadlock. If sufficient information to decide the reducibility of a node is not available at that node, the algorithm attempts reduction later in a lazy manner. We prove the correctness of the algorithm. The algorithm has a message complexity of 2e messages and a worst case time complexity of 2d hops, where e is the number of edges and d is the diameter of the WFG. The algorithm is shown to perform better in both time and message complexity than the best known distributed algorithms to detect distributed generalized deadlocks. We conjecture that the algorithm is optimal in the number of messages and time delay, among distributed algorithms to detect generalized deadlocks.
---
paper_title: Efficient detection and resolution of generalized distributed deadlocks

paper_content:

We present an efficient one-phase algorithm that consists of two concurrent sweeps of messages to detect generalized distributed deadlocks. In the outward sweep, the algorithm records a snapshot of a distributed wait-for-graph (WFG). In the inward sweep, the algorithm performs reduction of the recorded distributed WFG to check for a deadlock. The two sweeps can overlap in time at a process. We prove the correctness of the algorithm. The algorithm has a worst-case message complexity of 4e/spl minus/2n+2l and a time complexity of 2d hops, where e is the number of edges, n is the number of nodes, l is the number of leaf nodes, and d is the diameter of the WFG. This is a notable improvement over the existing algorithms to detect generalized deadlocks. >
---
paper_title: Optimal deadlock detection in distributed systems based on locally constructed wait-for graphs

paper_content:

We present a new algorithm for detecting generalized deadlocks in distributed systems. Our algorithm incrementally constructs and reduces a wait-for graph (WFG) at an initiator process. This WFG is then searched for deadlock. The proposed algorithm has two primary advantages: First, it avoids sending messages along the edges of the global wait-for graph (WFG), thereby achieving a worst-case message complexity of 2n, where n is the number of processes in the WFG. Since information must be obtained from every process reachable from the initiator, this is optimal to within a constant factor. All the existing algorithms for the same problem construct a distributed snapshot of the WFG. As this involves sending messages along the edges of the WFG, the best available message complexity among these algorithms is 4e-2n+2l, which is O(n/sup 2/) in the worst case, where e and l are the number of edges and leaves in the WFG, respectively. Second, since the information about a detected deadlock is readily available at the initiator process, rather than distributed among different processes, it significantly simplifies the task of deadlock resolution, and helps to reduce system overhead associated with the resolution. The time complexity of our algorithm is also better than or equal to the existing algorithms.
---
paper_title: Deadlock Models and a General Algorithm for Distributed Deadlock Detection

paper_content:

This paper deals with the problem of deadlock detection in asynchronous message passing systems in a system model that covers unspecified receptions and non-FIFO channels. It presents a hierarchy of deadlock models and deadlock detection problems. It abstracts deadlocks by a general deadlock model that has the same modeling power as the OR-AND model; however, it has much concise expressive power. An abstract general definition of deadlocks in distributed systems is presented that defines deadlocks independently of the underlying deadlock model. This formulation can be used to design a single distributed deadlock detection algorithm which uniformly addresses all deadlocks in the context of various request models such as AND, OR, AND-OR, and k-out-of-n requests. A simple generalized deadlock detection algorithm that uses a circulating token is presented to illustrate the concept. The algorithm is formally described and proven correct. Moreover, possible refinements of the basic solution concerning improvements of token routing and parallel implementation are outlined and evaluated. Extensions to individual and global termination issues are also addressed. Since the proposed deadlock detection algorithm is designed around the abstract definition of deadlocks, it has some very favorable features.
---
paper_title: Efficient detection and resolution of generalized distributed deadlocks

paper_content:

We present an efficient one-phase algorithm that consists of two concurrent sweeps of messages to detect generalized distributed deadlocks. In the outward sweep, the algorithm records a snapshot of a distributed wait-for-graph (WFG). In the inward sweep, the algorithm performs reduction of the recorded distributed WFG to check for a deadlock. The two sweeps can overlap in time at a process. We prove the correctness of the algorithm. The algorithm has a worst-case message complexity of 4e/spl minus/2n+2l and a time complexity of 2d hops, where e is the number of edges, n is the number of nodes, l is the number of leaf nodes, and d is the diameter of the WFG. This is a notable improvement over the existing algorithms to detect generalized deadlocks. >
---
paper_title: An Efficient Detection and Resolution of Generalized Deadlocks in Distributed Systems

paper_content:

In this paper, we propose a new algorithm to detect and resolve distributed deadlocks in the generalized model. The initiator of the proposed algorithm diffuses the probes along the outgoing edges of Wait-For Graph (WFG) and collects the replies that carry the dependency information between processes directly. However, the initiator simplifies the unblocking conditions of blocked nodes in response to a reply form an unblocked node and receives almost two replies from any node unlike the earlier algorithms. It finally declares all the nodes that have not been reduced as deadlocked. We also prove the correctness of the algorithm. It has a worst-case time complexity of d+1 and message complexity of less than e+2n where d is the diameter, e is the number of edges and n is the number of nodes in the WFG. Since the termination detection of the proposed algorithm is isolated from deadlock detection, it minimizes the message length into a constant without using any explicit technique. It is the significant improvement over the existing algorithms. It also minimizes additional rounds of messages to resolve deadlocks.
---
paper_title: Fast, centralized detection and resolution of distributed deadlocks in the generalized model

paper_content:

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.
---

Title: A Review of Distributed Deadlock Detection Techniques based on Diffusion Computation Approach

Section 1: INTRODUCTION
Description 1: This section introduces the concept of distributed systems, the issue of deadlock in such systems, and the importance of deadlock detection.

Section 2: MODELS OF DEADLOCKS
Description 2: This section provides a classification of deadlock detection algorithms based on different resource-request models.

Section 3: TYPES OF DEADLOCK DETECTION ALGORITHMS
Description 3: This section describes various types of deadlock detection algorithms including Path Pushing, Edge Chasing, Global State Detection, and Diffusion Computation based algorithms.

Section 4: DEADLOCK DETECTION BASED ON DIFFUSION COMPUTATION
Description 4: This section delves into the specifics of deadlock detection algorithms that use the diffusion computation approach, and compares it with other approaches like path pushing.

Section 5: Gabriel Bracha and Sam Toueg's Algorithm
Description 5: This section explains the algorithm developed by Gabriel Bracha and Sam Toueg for deadlock detection in distributed systems.

Section 6: Wang J Huang's Algorithm
Description 6: This section describes Wang J Huang's algorithm for deadlock detection, highlighting its phases and techniques.

Section 7: Kshemkalyani's Algorithm
Description 7: This section elaborates on Kshemkalyani's approach to detecting generalized deadlocks in replicated databases.

Section 8: Shigeng Cheng's Algorithm
Description 8: This section discusses Shigeng Cheng's algorithm and its stage-based approach for identifying deadlocks.

Section 9: Srinivasan Selvaraj's Algorithm
Description 9: This section outlines the centralized approach by Srinivasan Selvaraj and Rajaram Ramasamy for detecting generalized deadlocks.

Section 10: Soojung Lee's Algorithm
Description 10: This section details Soojung Lee's algorithm, focusing on its probing and deadlock detection and resolution phases.

Section 11: CONCLUSION
Description 11: This section provides a summary of the reviewed techniques, their comparative analysis, and identifies areas for further research in distributed deadlock detection.