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

Natalija Krivokapic, Alfons Kemper, Ehud Gudes: Deadlock Detection in Distributed Database Systems: A New Algorithm and a Comparative Performance Analysis. VLDB J. 8(2): 79-100(1999)

@article{DBLP:journals/vldb/KrivokapicKG99,
  author    = {Natalija Krivokapic and
               Alfons Kemper and
               Ehud Gudes},
  title     = {Deadlock Detection in Distributed Database Systems: A New Algorithm
               and a Comparative Performance Analysis},
  journal   = {VLDB J.},
  volume    = {8},
  number    = {2},
  year      = {1999},
  pages     = {79-100},
  ee        = {db/journals/vldb/KrivokapicKG99.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper attempts a comprehensive study of deadlock detection in distributed database systems. First, the two predominant deadlock models in these systems and the four different distributed deadlock detection approaches are discussed. 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 locality of the distributed system will be responded to by automatically creating new DDAs while the obsolete ones terminate. In this paper, we also compare the most competitive representative 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 experiments we carried out indicate that our newly proposed deadlock detection algorithm outperforms the other algorithms in the vast majority of configurations and workloads and, in contrast to all other algorithms, is very robust with respect to differing load and access profiles.

Key Words

Distributed database systems - Deadlock detection - Comparative performance analysis - Simulation study

Copyright © 1999 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

Citation Page

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 5 Issue 2, JACM, VLDB-J, POS, ..." and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An5-2 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

References

[ACM87]: Rakesh Agrawal, Michael J. Carey, Lawrence W. McVoy: The Performance of Alternative Strategies for Dealing with Deadlocks in Database Management Systems. IEEE Trans. Software Eng. 13(12): 1348-1363(1987)
[Bad86]: Dushan Z. Badal: The Distributed Deadlock Detection Algorithm. ACM Trans. Comput. Syst. 4(4): 320-337(1986)
[BHG87]: Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents
[BHRS95]: ...
[BN97]: Philip A. Bernstein, Eric Newcomer: Principles of Transaction Processing for Systems Professionals. Morgan Kaufmann 1996, ISBN 1-55860-415-4
[BO81]: Catriel Beeri, Ron Obermarck: A Resource Class Independent Deadlock Detection Algorithm. VLDB 1981: 166-178
[BT87]: Gabriel Bracha, Sam Toueg: Distributed Deadlock Detection. Distributed Computing 2(3): 127-138(1987)
[Buk92]: Omran A. Bukhres: Performance Comparisons of Distributed Deadlock Detection Algorithms. ICDE 1992: 210-217
[CDAS96]: Shigang Chen, Yi Deng, Paul C. Attie, Wei Sun: Optimal Deadlock Detection in Distributed Systems Based on Locally Constructed Wait-for Graphs. ICDCS 1996: 613-619
[Cha82]: Ernest J. H. Chang: Echo Algorithms: Depth Parallel Operations on General Graphs. IEEE Trans. Software Eng. 8(4): 391-401(1982)
[Cho90]: Alok N. Choudhary: Cost of Distributed Deadlock Detection: A Performance Study. ICDE 1990: 174-181
[CKST89]: Alok N. Choudhary, Walter H. Kohler, John A. Stankovic, Donald F. Towsley: A Modified Priority Based Probe Algorithm for Distributed Deadlock Detection and Resolution. IEEE Trans. Software Eng. 15(1): 10-17(1989)
[CL85]: K. Mani Chandy, Leslie Lamport: Distributed Snapshots: Determining Global States of Distributed Systems. ACM Trans. Comput. Syst. 3(1): 63-75(1985)
[CM82]: K. Mani Chandy, Jayadev Misra: A Distributed Algorithm for Detecting Resource Deadlocks in Distributed Systems. PODC 1982: 157-164
[CMH83]: K. Mani Chandy, Jayadev Misra, Laura M. Haas: Distributed Deadlock Detection. ACM Trans. Comput. Syst. 1(2): 144-156(1983)
[DS80]: Edsger W. Dijkstra, Carel S. Scholten: Termination Detection for Diffusing Computations. Inf. Process. Lett. 11(1): 1-4(1980)
[Elm86]: Ahmed K. Elmagarmid: A Survey of Distributed Deadlock Algorithms. SIGMOD Record 15(3): 37-45(1986)
[ESL88]: Ahmed K. Elmagarmid, Neelam Soundararajan, Ming T. Liu: A Distributed Deadlock Detection and Resolution Algorithm and Its Correctness Proof. IEEE Trans. Software Eng. 14(10): 1443-1452(1988)
[GR93]: Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents
[GS80]: Virgil D. Gligor, Susan H. Shattuck: On Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 6(5): 435-440(1980)
[Hof94]: Micha Hofri: On Timeout for Global Deadlock Detection in Decentralized Database Systems. Inf. Process. Lett. 51(6): 295-302(1994)
[KGI+97]: ...
[Kna87]: Edgar Knapp: Deadlock Detection in Distributed Databases. ACM Comput. Surv. 19(4): 303-328(1987)
[Kor83]: Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983)
[KS91]: Ajay D. Kshemkalyani, Mukesh Singhal: Invariant-Based Verification of a Distributed Deadlock Detection Algorithm. IEEE Trans. Software Eng. 17(8): 789-799(1991)
[KS94a]: Ajay D. Kshemkalyani, Mukesh Singhal: Efficient Detection and Resolution of Generalized Distributed Deadlocks. IEEE Trans. Software Eng. 20(1): 43-54(1994)
[KS94b]: ...
[KS97]: Ajay D. Kshemkalyani, Mukesh Singhal: Distributed Detection of Generalized Deadlocks. ICDCS 1997: 0-
[LK95]: Soojung Lee, Junguk L. Kim: An Efficient Distributed Deadlock Detection Algorithm. ICDCS 1995: 169-178
[LMB97]: ...
[MC82]: Jayadev Misra, K. Mani Chandy: Termination Detection of Diffusing Computations in Communicating Sequential Processes. ACM Trans. Program. Lang. Syst. 4(1): 37-43(1982)
[MM79]: Daniel A. Menascé, Richard R. Muntz: Locking and Deadlock Detection in Distributed Data Bases. IEEE Trans. Software Eng. 5(3): 195-202(1979)
[Obe82]: Ron Obermarck: Distributed Deadlock Detection Algorithm. ACM Trans. Database Syst. 7(2): 187-208(1982)
[RB88]: Marina Roesler, Walter A. Burkhard: Deadlock Resolution and Semantic Lock Models in Object-Oriented Distributed Systems. SIGMOD Conference 1988: 361-370
[RB89]: Marina Roesler, Walter A. Burkhard: Resolution of Deadlocks in Object-Oriented Distributed Systems. IEEE Trans. Computers 38(8): 1212-1224(1989)
[RBC88]: Marina Roesler, Walter A. Burkhard, Kenneth B. Cooper: Efficient Deadlock Resolution for Lock-Based Concurrency Control Schemes. ICDCS 1988: 224-233
[RHGL97]: Fernando de Ferreira Rezende, Theo Härder, Andreas Gloeckner, Jörg Lutze: Detection Arcs for Deadlock Management in Nested Transactions and their Performance. BNCOD 1997: 54-68
[Ruk91]: Marta Rukoz: Hierarchical Deadlock Detection for Nested Transactions. Distributed Computing 4: 123-129(1991)
[SAL+96]: Michael Stonebraker, Paul M. Aoki, Witold Litwin, Avi Pfeffer, Adam Sah, Jeff Sidell, Carl Staelin, Andrew Yu: Mariposa: A Wide-Area Distributed Database System. VLDB J. 5(1): 48-63(1996)
[SH89]: Beverly A. Sanders, Philipp A. Heuberger: Distributed Deadlock Detection and Resolution with Probes. WDAG 1989: 207-218
[Sin89]: Mukesh Singhal: Deadlock Detection in Distributed Systems. IEEE Computer 22(11): 37-48(1989)
[SN85]: Mukul K. Sinha, N. Natarajan: A Priority Based Distributed Deadlock Detection Algorithm. IEEE Trans. Software Eng. 11(1): 67-80(1985)
[SS84]: Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984)
[WB85]: Gene T. J. Wuu, Arthur J. Bernstein: False Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 11(8): 820-821(1985)
[WDH+81]: R. Williams, Dean Daniels, Laura M. Haas, George Lapis, Bruce G. Lindsay, Pui Ng, Ron Obermarck, Patricia G. Selinger, Adrian Walker, Paul F. Wilms, Robert A. Yost: R*: An Overview of the Architecture. JCDKB 1982: 1-27
[YHL94]: Chim-fu Yeung, Sheung-lun Hung, Kam-yiu Lam: Performance Evaluation of a New Distributed Deadlock Detection Algorithm. SIGMOD Record 23(3): 21-26(1994)