Deadlock Detection in Distributed Database Systems: A New Algorithm and a Comparative Performance Analysis

Abstract. This paper attempts a comprehensive study of dead-lock detection in distributed database systems. First the two predominant deadlock models in these systems, and the four different distributed deadlock detection approaches are dis-cussed. Afterwards, a new deadlock detection algorithm is presented. The algorithm is based on dynamically creating Deadlock Detection Agents (DDAs) each being responsible for detecting deadlocks in one connected component of the global Wait-For-Graph (WFG). The DDA scheme is a “self-tuning ” system: After an initial warm-up phase, dedicated DDAs will be formed for “centers of locality”, i.e., parts of the system where many conflicts occur. A dynamic shift in lo-cality of the distributed system will be responded to by auto-matically creating new DDAs while the obsolete ones termi-nate. In this paper we also compare the most competitive rep-resentative of each class of algorithms suitable for distributed database systems based on a simulation model, and point out their relative strengths and weaknesses. The extensive exper-iments we carried out indicate that our newly proposed dead-lock detection algorithm outperforms the other algorithms in the vast majority of configurations and work loads and—in contrast to all other algorithms—is very robust with respect to differing load and access profiles.