dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

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 ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Bad86]
Dushan Z. Badal: The Distributed Deadlock Detection Algorithm. ACM Trans. Comput. Syst. 4(4): 320-337(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BHG87]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BHRS95]
...
[BN97]
Philip A. Bernstein, Eric Newcomer: Principles of Transaction Processing for Systems Professionals. Morgan Kaufmann 1996, ISBN 1-55860-415-4
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BO81]
Catriel Beeri, Ron Obermarck: A Resource Class Independent Deadlock Detection Algorithm. VLDB 1981: 166-178 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BT87]
Gabriel Bracha, Sam Toueg: Distributed Deadlock Detection. Distributed Computing 2(3): 127-138(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Buk92]
Omran A. Bukhres: Performance Comparisons of Distributed Deadlock Detection Algorithms. ICDE 1992: 210-217 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cha82]
Ernest J. H. Chang: Echo Algorithms: Depth Parallel Operations on General Graphs. IEEE Trans. Software Eng. 8(4): 391-401(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cho90]
Alok N. Choudhary: Cost of Distributed Deadlock Detection: A Performance Study. ICDE 1990: 174-181 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CL85]
K. Mani Chandy, Leslie Lamport: Distributed Snapshots: Determining Global States of Distributed Systems. ACM Trans. Comput. Syst. 3(1): 63-75(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CM82]
K. Mani Chandy, Jayadev Misra: A Distributed Algorithm for Detecting Resource Deadlocks in Distributed Systems. PODC 1982: 157-164 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CMH83]
K. Mani Chandy, Jayadev Misra, Laura M. Haas: Distributed Deadlock Detection. ACM Trans. Comput. Syst. 1(2): 144-156(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[DS80]
Edsger W. Dijkstra, Carel S. Scholten: Termination Detection for Diffusing Computations. Inf. Process. Lett. 11(1): 1-4(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Elm86]
Ahmed K. Elmagarmid: A Survey of Distributed Deadlock Algorithms. SIGMOD Record 15(3): 37-45(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GR93]
Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GS80]
Virgil D. Gligor, Susan H. Shattuck: On Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 6(5): 435-440(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hof94]
Micha Hofri: On Timeout for Global Deadlock Detection in Decentralized Database Systems. Inf. Process. Lett. 51(6): 295-302(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KGI+97]
...
[Kna87]
Edgar Knapp: Deadlock Detection in Distributed Databases. ACM Comput. Surv. 19(4): 303-328(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kor83]
Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS91]
Ajay D. Kshemkalyani, Mukesh Singhal: Invariant-Based Verification of a Distributed Deadlock Detection Algorithm. IEEE Trans. Software Eng. 17(8): 789-799(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS94a]
Ajay D. Kshemkalyani, Mukesh Singhal: Efficient Detection and Resolution of Generalized Distributed Deadlocks. IEEE Trans. Software Eng. 20(1): 43-54(1994) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KS94b]
...
[KS97]
Ajay D. Kshemkalyani, Mukesh Singhal: Distributed Detection of Generalized Deadlocks. ICDCS 1997: 0- CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LK95]
Soojung Lee, Junguk L. Kim: An Efficient Distributed Deadlock Detection Algorithm. ICDCS 1995: 169-178 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MM79]
Daniel A. Menascé, Richard R. Muntz: Locking and Deadlock Detection in Distributed Data Bases. IEEE Trans. Software Eng. 5(3): 195-202(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Obe82]
Ron Obermarck: Distributed Deadlock Detection Algorithm. ACM Trans. Database Syst. 7(2): 187-208(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RB88]
Marina Roesler, Walter A. Burkhard: Deadlock Resolution and Semantic Lock Models in Object-Oriented Distributed Systems. SIGMOD Conference 1988: 361-370 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RB89]
Marina Roesler, Walter A. Burkhard: Resolution of Deadlocks in Object-Oriented Distributed Systems. IEEE Trans. Computers 38(8): 1212-1224(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RBC88]
Marina Roesler, Walter A. Burkhard, Kenneth B. Cooper: Efficient Deadlock Resolution for Lock-Based Concurrency Control Schemes. ICDCS 1988: 224-233 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ruk91]
Marta Rukoz: Hierarchical Deadlock Detection for Nested Transactions. Distributed Computing 4: 123-129(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SH89]
Beverly A. Sanders, Philipp A. Heuberger: Distributed Deadlock Detection and Resolution with Probes. WDAG 1989: 207-218 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sin89]
Mukesh Singhal: Deadlock Detection in Distributed Systems. IEEE Computer 22(11): 37-48(1989) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SN85]
Mukul K. Sinha, N. Natarajan: A Priority Based Distributed Deadlock Detection Algorithm. IEEE Trans. Software Eng. 11(1): 67-80(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SS84]
Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WB85]
Gene T. J. Wuu, Arthur J. Bernstein: False Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 11(8): 820-821(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Fri Sep 14 18:29:13 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page