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

@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

Key Words

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)

ACM SIGMOD Anthology

• 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

• 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) BibTeX

[Bad86]

Dushan Z. Badal: The Distributed Deadlock Detection Algorithm. ACM Trans. Comput. Syst. 4(4): 320-337(1986) BibTeX

[BHG87]

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX

[BHRS95]

...

[BN97]

Philip A. Bernstein, Eric Newcomer: Principles of Transaction Processing for Systems Professionals. Morgan Kaufmann 1996, ISBN 1-55860-415-4
BibTeX

[BO81]

Catriel Beeri, Ron Obermarck: A Resource Class Independent Deadlock Detection Algorithm. VLDB 1981: 166-178 BibTeX

[BT87]

Gabriel Bracha, Sam Toueg: Distributed Deadlock Detection. Distributed Computing 2(3): 127-138(1987) BibTeX

[Buk92]

Omran A. Bukhres: Performance Comparisons of Distributed Deadlock Detection Algorithms. ICDE 1992: 210-217 BibTeX

[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 BibTeX

[Cha82]

Ernest J. H. Chang: Echo Algorithms: Depth Parallel Operations on General Graphs. IEEE Trans. Software Eng. 8(4): 391-401(1982) BibTeX

[Cho90]

Alok N. Choudhary: Cost of Distributed Deadlock Detection: A Performance Study. ICDE 1990: 174-181 BibTeX

[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) BibTeX

[CL85]

K. Mani Chandy, Leslie Lamport: Distributed Snapshots: Determining Global States of Distributed Systems. ACM Trans. Comput. Syst. 3(1): 63-75(1985) BibTeX

[CM82]

K. Mani Chandy, Jayadev Misra: A Distributed Algorithm for Detecting Resource Deadlocks in Distributed Systems. PODC 1982: 157-164 BibTeX

[CMH83]

K. Mani Chandy, Jayadev Misra, Laura M. Haas: Distributed Deadlock Detection. ACM Trans. Comput. Syst. 1(2): 144-156(1983) BibTeX

[DS80]

Edsger W. Dijkstra, Carel S. Scholten: Termination Detection for Diffusing Computations. Inf. Process. Lett. 11(1): 1-4(1980) BibTeX

[Elm86]

Ahmed K. Elmagarmid: A Survey of Distributed Deadlock Algorithms. SIGMOD Record 15(3): 37-45(1986) BibTeX

[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) BibTeX

[GR93]

Jim Gray, Andreas Reuter: Transaction Processing: Concepts and Techniques. Morgan Kaufmann 1993, ISBN 1-55860-190-2
Contents BibTeX

[GS80]

Virgil D. Gligor, Susan H. Shattuck: On Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 6(5): 435-440(1980) BibTeX

[Hof94]

Micha Hofri: On Timeout for Global Deadlock Detection in Decentralized Database Systems. Inf. Process. Lett. 51(6): 295-302(1994) BibTeX

[KGI+97]

...

[Kna87]

Edgar Knapp: Deadlock Detection in Distributed Databases. ACM Comput. Surv. 19(4): 303-328(1987) BibTeX

[Kor83]

Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) BibTeX

[KS91]

Ajay D. Kshemkalyani, Mukesh Singhal: Invariant-Based Verification of a Distributed Deadlock Detection Algorithm. IEEE Trans. Software Eng. 17(8): 789-799(1991) BibTeX

[KS94a]

Ajay D. Kshemkalyani, Mukesh Singhal: Efficient Detection and Resolution of Generalized Distributed Deadlocks. IEEE Trans. Software Eng. 20(1): 43-54(1994) BibTeX

[KS94b]

...

[KS97]

Ajay D. Kshemkalyani, Mukesh Singhal: Distributed Detection of Generalized Deadlocks. ICDCS 1997: 0- BibTeX

[LK95]

Soojung Lee, Junguk L. Kim: An Efficient Distributed Deadlock Detection Algorithm. ICDCS 1995: 169-178 BibTeX

[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) BibTeX

[MM79]

Daniel A. Menascé, Richard R. Muntz: Locking and Deadlock Detection in Distributed Data Bases. IEEE Trans. Software Eng. 5(3): 195-202(1979) BibTeX

[Obe82]

Ron Obermarck: Distributed Deadlock Detection Algorithm. ACM Trans. Database Syst. 7(2): 187-208(1982) BibTeX

[RB88]

Marina Roesler, Walter A. Burkhard: Deadlock Resolution and Semantic Lock Models in Object-Oriented Distributed Systems. SIGMOD Conference 1988: 361-370 BibTeX

[RB89]

Marina Roesler, Walter A. Burkhard: Resolution of Deadlocks in Object-Oriented Distributed Systems. IEEE Trans. Computers 38(8): 1212-1224(1989) BibTeX

[RBC88]

Marina Roesler, Walter A. Burkhard, Kenneth B. Cooper: Efficient Deadlock Resolution for Lock-Based Concurrency Control Schemes. ICDCS 1988: 224-233 BibTeX

[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 BibTeX

[Ruk91]

Marta Rukoz: Hierarchical Deadlock Detection for Nested Transactions. Distributed Computing 4: 123-129(1991) BibTeX

[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) BibTeX

[SH89]

Beverly A. Sanders, Philipp A. Heuberger: Distributed Deadlock Detection and Resolution with Probes. WDAG 1989: 207-218 BibTeX

[Sin89]

Mukesh Singhal: Deadlock Detection in Distributed Systems. IEEE Computer 22(11): 37-48(1989) BibTeX

[SN85]

Mukul K. Sinha, N. Natarajan: A Priority Based Distributed Deadlock Detection Algorithm. IEEE Trans. Software Eng. 11(1): 67-80(1985) BibTeX

[SS84]

Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984) BibTeX

[WB85]

Gene T. J. Wuu, Arthur J. Bernstein: False Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 11(8): 820-821(1985) BibTeX

[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 BibTeX

[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) BibTeX