Search

This work introduces a duplication-based deadlock resolution (DBDR) scheme in clustered directed acyclic graphs using three methods for duplicating a task. The scheme can be embedded within any clustering technique for handling synchronous communication with an added cost of O(|E| + (|V|)2). The main objective of task duplication, besides to resolving deadlocks, has been the reduction of communication cost and the improvement in the program computation to communication ratio. The embedding of the DBDR scheme within a clustering technique is shown along with the analysis of its complexity. A comparison between deadlock resolution strategy using the DBDR and deadlock avoidance strategy using the same clustering technique is given.

Deadlock detection and resolution is one of the major components of a successful distributed database management system. In this article, we discuss deadlock detection and resolution strategies and present two approaches for detecting and resolving deadlocks in both general distributed database systems and distributed real-time database systems. Our first approach is to collect information on the connectivity of nodes of the overall Transaction Wait-For Graph (TWFG) of the distributed database system and then use these connectivities information to build a local TWFG at each node of the overall TWFG. We then detect the deadlocks by locating the cycles in each local TWFG. To resolve the deadlocks, the nodes involved in those cycles in each local TWFG, are removed until there is no cycle in the local TWFGs. Our second approach continuously checks for the occurrence of a deadlock between different transaction trees. As soon as it detects a deadlock, it resolves it by aborting one of the transaction tree which has been initiated more recently. Some of the advantages of our approaches over the approaches which use Probe messages are: (1) no extra storage required to store different probe messages, (2) no false (Phantom) deadlocks are reported, (3) detects and resolves all deadlocks. In addition, our approaches use less message and time to detect and resolve all deadlocks in existing TWFG of the distributed database system.

Various proposals for Deadlock Detection/Resolution algorithms in distributed systems with AND model have been designed with the purpose of reducing the number of messages involved on detect and resolve deadlocks. The solutions exhibit high degree of liveness but fail in the intuitive safety condition only true deadlocks are resolved. This irregular behaviour of algorithms produces resolutions of false deadlocks, that is, nonexisting or currently being resolved deadlocks. This paper introduces an algorithm free of false deadlock resolutions. The algorithm is probe-based, uses priority of nodes, and stores simple information of messages in order to avoid false deadlocks resolutions. The algorithm is formally proven to verify the safety condition using the Input/Output Automata Model as the basis for the formalism.

In this paper we study the problem of deadlock detection in multidatabase systems. In such environments, global deadlock mechanisms perform poorly since they often detect phantom deadlocks and perform duplicate work. With this work we allow the implicit collaboration between the global and the local deadlock resolution schemes, which avoids duplicate work and we devise mechanisms which reduce the number of unnecessary transaction abortions caused by phantom deadlocks. Also, our scheme introduces smaller overhead, when compared to related work. Moreover, our scheme makes no unrealistic assumptions about the computational environment (unlike related work) and is thus of practical use. Finally, we present an empirical performance study through detailed simulations of known approaches and study MDBS deadlock detection experimentally.

There are few studies of deadlock resolution in the real-time distributed database environment. A specially designed distributed deadlock detection algorithm known as the Enhanced Probe-Based Algorithm (EPBA) was evaluated by the authors and has found to be very effective. The present work is carried out to evaluate the EPBA for the firm real-time distributed database environment. The study also compares its performance with other existing deadlock resolution algorithms such as the timeouts algorithm and the global sequential locking algorithm. Results indicated that under high data contention and with slack transaction deadlines, the EPBA approach outperforms all the other deadlock resolution methods.

Distributed deadlock detection requires identifying the presence of certain properties in the global state of distributed systems. Distributed deadlock detection is complicated due to the lack of both global memory and a common physical clock, and due to unpredictable message delays. We characterize the formation and detection of distributed deadlocks in terms of the contents of local memory of distributed nodes/sites. We describe how the interaction between deadlock detection and deadlock resolution can lead to the detection of false deadlocks that are impossible to avoid due to inherent system limitations. We define shadow, phantom, and pseudo deadlocks in the proposed framework. We give examples of existing incorrect deadlock detection algorithms to illustrate how they violate the developed requirements for distributed deadlock detection. The characterization provides an insight into the properties of distributed deadlocks, expresses inherent limitations of distributed deadlock detection, and yields new correctness criteria for distributed deadlock detection algorithms.

One problem that has often been overlooked in research in flexible manufacturing systems (FMSs) design and operation is deadlocking. An FMS deadlock is a situation where machines have been allocated parts so that further part movement is inhibited. In our earlier paper, a procedure to detect deadlocks was presented. In this paper, two approaches to resolve deadlock problems, namely avoidance and recovery, are presented and analyzed. These approaches can be used to avoid or resolve deadlocks during active control of the FMS. A simulation study to compare deadlock resolution approaches to conventional approaches for avoiding deadlocks is also presented. Results of the analysis are presented.

A distributed scheme for dynamically detecting resource deadlocks is presented. The proposed scheme dynamically partitions the processes in the system into a set of groups and defines dependency relations between any two processes within a group (group information). This process grouping enables the detection of the deadlock without chasing all the edges of the cycle since the group information remains valid until it is updated again. Since the group information is updated during run-time, there is no separate detection phase in the proposed scheme and the deadlock is detected dynamically during run-time. The proposed scheme ensures that only one process in the cycle detects deadlock, which simplifies the process of deadlock resolution. The deadlock resolution rules that make the group information remain valid after the resolution of the deadlock are also presented. Performance of the proposed scheme is discussed through simulation.

In a distributed system, a set of processes may sometimes get involved in a communication deadlock. This is a situation where each process in the group waits for some process to communicate with it, but no other process is attempting communication. A new algorithm for deadlock detection in the communication model is presented. The proposed scheme is based on a new approach to the problem of distributed knot detection, which appears to be more efficient and simpler than existing ones. The resulting deadlock detection algorithm has the feature that when it terminates, the initiator knows all the processes that have caused the deadlock and may subsequently proceed to deadlock resolution.

This paper presents Petri net modeling of a five-robot-five-assembly-line system based on four different deadlock avoidance schemes: conventional scheme, full synchronization scheme, global semaphore scheme, and partial synchronzation scheme. In order to explore such issues as the system performance and control stucture complexity, this paper conducts performance analysis for this system based on all schemes using stochastic Petri nets. The interesting results presented include that: 1. Any possible system deadlock can seriously degrade the system performance even if effective deadlock resolution techniques are available; 2. Conservative use of resource is likely to be the best policy; and 3. Higher resource utilization may not necessarily imply higher system production rates in a resource-sharing environment. The related results need to be further explored for the larger resource-sharing discrete event systems. The future research will detail the performance analysis under various timing assumptions for the five-robot-five-assembly-line system and derive the results for general cases.