Deadlock detection and resolution in distributed processing systems (ddbms, synchronization)
Ahmed K. Elmagarmid · 1985
The availability of distributed databases is directly affected by the timely detection and resolution of deadlocks. Consequently, mechanisms are needed to make deadlock detection algorithms resilient to failures. Presented first in this dissertation is a centralized algorithm that allows transactions to have multiple requests outstanding. Next, a new distributed deadlock detection algorithm (DDDA) is presented, using a global detector (GD) to detect global deadlocks and local detectors (LDs) to detect local deadlocks. This algorithm essentially identifies transaction-resource interactions that may cause global (multisite) deadlocks. Such interactions are reported to the global controller, while the remaining interactions are handled locally. In order to make the DDDA fault-tolerant, three procedures have been incorporated to handle failures of the controller, failures of any of the local sites, and failures of communication links. This enhanced algorithm, called FTDDDA, improves the overall performance of the database system by improving resiliency of the deadlock detection service. Third, a deadlock detection algorithm utilizing a transaction-wait-for (TWF) graph is presented. It is a fully disjoint algorithm which allows multiple outstanding requests. The proposed algorithm can achieve improved overall performance by using multiple disjoint controllers coupled with the two-phase property while maintaining the simplicity of centralized schemes. The detection step is divided into two phases. Phase I analyzes the conditions of the system of interacting transactions and invokes phase 2 only if conditions are possible for deadlocks to occur. Phase 2 performs the actual cycle detection. The proposed algorithm can be used in distributed database systems, as well as in transaction-processing systems. Certain results regarding the complexity of the algorithm are given in the worst, average and best cases, with special emphasis on the worst case analysis. Fourth, an algorithm which combines deadlock detection and avoidance is given. This algorithm uses concurrent transaction controllers and resource coordinators to achieve maximum distribution. The language of CSP is used to describe this algorithm. In addition, we show that all deadlocks will be detected by this algorithm and further that the communicating components of this algorithm are deadlock free. Finally, two efficient deadlock resolution protocols are given along with some guidelines to be used in choosing a transaction for abortion.