Distribute Algorithms for Efficient Deadlock Detection and Resolution

Authors:Yang, Yiechan, Department of Computer ScienceUniversity of Virginia Hsu, Lifeng, Department of Computer ScienceUniversity of Virginia Son, S, Department of Computer ScienceUniversity of Virginia

In this paper we present two efficient distributed deadlock detection and resolution algorithms which combine both path-pushing and edge-chasing techniques to detect and resolve deadlocks in a distributed database system. By locally building up the PRAG (Partial Resource Allocation Graph)‘ information for every transaction on each site through edge - chasing and path-pushing, these algorithms _not only have transactions wait-for information but also have resources allocation information. Therefore, as soon as a deadlock cycle is going to form on a site, these algorithms can immediately detect it. The first algorithm starts the deadlock resolution right away whenever a "potential" deadlock cycle is detected. Thus, this algorithm can not completely avoid the detection of false deadlocks. However, it uses an efficient cleanup mechanism to reduce the probability of detecting false deadlocks. The second algorithm does not start the deadlock resolution immediately when a forming of deadlock cycle is detected. Instead, it validates if the potential deadlock cycle is a true deadlock. It starts the deadlock resolution only when a true deadlock is detected. Although this algorithm satisfies the correctness criterion of no false deadlock detection. it delays the true deadlock detection and resolution. We claim that both algorithms are very efficient while comparing them with other distributed deadlock detection algorithms in the literature.
Note: Abstract extracted from PDF file via OCR

All rights reserved (no additional license for public reuse)
Source Citation:

Yang, Yiechan, Lifeng Hsu, and S Son. "Distribute Algorithms for Efficient Deadlock Detection and Resolution." University of Virginia Dept. of Computer Science Tech Report (1992).

University of Virginia, Department of Computer Science
Published Date: