ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Deadlock Detection in Distributed Databases.

Edgar Knapp: Deadlock Detection in Distributed Databases. ACM Comput. Surv. 19(4): 303-328(1987)
@article{DBLP:journals/csur/Knapp87,
  author    = {Edgar Knapp},
  title     = {Deadlock Detection in Distributed Databases},
  journal   = {ACM Comput. Surv.},
  volume    = {19},
  number    = {4},
  year      = {1987},
  pages     = {303-328},
  ee        = {db/journals/csur/Knapp87.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The problem of deadlock detection in distributed systems has undergone extensive study. An important application relates to distributed database systems. A uniform model in which published algorithms can be cast is given, and the fundamental principles on which distributed deadlock detection schemes are based are presented. These principles represent mechanisms for developing distributed algorithms in general and deadlock detection schemes in particular. In addition, a hierarchy of deadlock models is presented; each model is characterized by the restrictions that are imposed upon the form resource requests can assume. The hierarchy includes the well-known models of resource and communication deadlock. Algorithms are classified according to both the underlying principles and the generality of resource requests they permit. A number of algorithms are discussed in detail, and their complexity in terms of the number of messages employed is compared. The point is made that correctness proofs for such algorithms using operational arguments are cumbersome and error prone and, therefore, that only completely formal proofs are sufficient for demonstrating correctness.

Copyright © 1987 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

Citation Page

References

[Awerbuch and Micali 1986]
Baruch Awerbuch, Silvio Micali: Dynamic deadlock resolution protocols (Extended Abstract). FOCS 1986: 196-207 BibTeX
[Bernstein et al. 1987]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
[Bracha and Toueg 1983]
...
[Bracha and Toueg 1984]
Gabriel Bracha, Sam Toueg: A Distributed Algorithm for Generalized Deadlock Detection. PODC 1984: 285-301 BibTeX
[Chandy and Lamport 1985]
K. Mani Chandy, Leslie Lamport: Distributed Snapshots: Determining Global States of Distributed Systems. ACM Trans. Comput. Syst. 3(1): 63-75(1985) BibTeX
[Chandy and Misra 1982]
K. Mani Chandy, Jayadev Misra: A Distributed Algorithm for Detecting Resource Deadlocks in Distributed Systems. PODC 1982: 157-164 BibTeX
[Chandy and Misra 1986]
K. Mani Chandy, Jayadev Misra: An Example of Stepwise Refinement of Distributed Programs: Quiescence Detection. ACM Trans. Program. Lang. Syst. 8(3): 326-343(1986) BibTeX
[Chandy et al. 1983]
K. Mani Chandy, Jayadev Misra, Laura M. Haas: Distributed Deadlock Detection. ACM Trans. Comput. Syst. 1(2): 144-156(1983) BibTeX
[Chang 1982]
Ernest J. H. Chang: Echo Algorithms: Depth Parallel Operations on General Graphs. IEEE Trans. Software Eng. 8(4): 391-401(1982) BibTeX
[Dijkstra and Scholten 1980]
Edsger W. Dijkstra, Carel S. Scholten: Termination Detection for Diffusing Computations. Inf. Process. Lett. 11(1): 1-4(1980) BibTeX
[Dijkstra et al. 1983]
Edsger W. Dijkstra, W. H. J. Feijen, A. J. M. van Gasteren: Derivation of a Termination Detection Algorithm for Distributed Computations. Inf. Process. Lett. 16(5): 217-219(1983) BibTeX
[Elmagarmid 1985]
...
[Elmagarmid 1986]
Ahmed K. Elmagarmid: A Survey of Distributed Deadlock Algorithms. SIGMOD Record 15(3): 37-45(1986) BibTeX
[Gafni 1986]
...
[Gifford 1979]
David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX
[Gligor and Shattuck 1980]
Virgil D. Gligor, Susan H. Shattuck: On Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 6(5): 435-440(1980) BibTeX
[Gray et al. 1981]
Jim Gray, Pete Homan, Henry F. Korth, Ron Obermarck: A Straw Man Analysis of the Probability of Waiting and Deadlock in a Database System. Berkeley Workshop 1981: 125 BibTeX
[Haas 1981]
...
[Haas and Mohan 1983]
...
[Helary et al. 1987]
Jean-Michel Hélary, Claude Jard, Noël Plouzeau, Michel Raynal: Detection of Stable Properties in Distributed Applications. PODC 1987: 125-136 BibTeX
[Hermann and Chandy 1983]
...
[Ho and Ramamoorthy]
Gary S. Ho, C. V. Ramamoorthy: Protocols for Deadlock Detection in Distributed Database Systems. IEEE Trans. Software Eng. 8(6): 554-557(1982) BibTeX
[Holt 1972]
Richard C. Holt: Some Deadlock Properties of Computer Systems. ACM Comput. Surv. 4(3): 179-196(1972) BibTeX
[Jagannathan and Vasudevan 1982]
...
[Lamport 1978]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX
[Menasce and Muntz 1979]
Daniel A. Menascé, Richard R. Muntz: Locking and Deadlock Detection in Distributed Data Bases. IEEE Trans. Software Eng. 5(3): 195-202(1979) BibTeX
[Misra 1983]
Jayadev Misra: Detecting Termination of Distributed Computations Using Markers. PODC 1983: 290-294 BibTeX
[Misra and Chandy 1982a]
Jayadev Misra, K. Mani Chandy: A Distributed Graph Algorithm: Knot Detection. ACM Trans. Program. Lang. Syst. 4(4): 678-686(1982) BibTeX
[Misra and Chandy 1982b]
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
[Mitchell and Merritt 1984]
Don P. Mitchell, Michael Merritt: A Distributed Algorithm for Deadlock Detection and Resolution. PODC 1984: 282-284 BibTeX
[Natarajan 1986]
N. Natarajan: A Distributed Scheme for Detecting Communication Deadlocks. IEEE Trans. Software Eng. 12(4): 531-537(1986) BibTeX
[Obermarck 1980]
...
[Obermarck 1982]
Ron Obermarck: Distributed Deadlock Detection Algorithm. ACM Trans. Database Syst. 7(2): 187-208(1982) BibTeX
[Papadimitriou 1987]
Christos H. Papadimitriou: The Theory of Database Concurrency Control. Computer Science Press 1986, ISBN 0-88175-027-1
BibTeX
[Räuchle and Toueg 1983]
Thomas Räuchle, Sam Toueg: Exposure to Deadlock for Communicating Processes is Hard to Detect. Inf. Process. Lett. 21(2): 63-68(1985) BibTeX
[Sinha and Natarajan 1984]
Mukul K. Sinha, N. Natarajan: A Distributed Deadlock Detection Algorithm Based on Timestamps. ICDCS 1984: 546-556 BibTeX
[Zobel 1983]
...
[Badal and Gehl 1983]
Dushan Z. Badal, M. T. Gehl: On Deadlock Detection in Distributed Computing Systems. INFOCOM 1983: 36-45 BibTeX
[Bracha 1985]
...
[Cohen and Lehmann 1982]
Shimon Cohen, Daniel J. Lehmann: Dynamic Systems and Their Distributed Termination. PODC 1982: 29-33 BibTeX
[Dijkstra 1982]
...
[Francez 1980]
Nissim Francez: Distributed Termination. ACM Trans. Program. Lang. Syst. 2(1): 42-55(1980) BibTeX
[Francez and Rodeh 1982]
Nissim Francez, Michael Rodeh: Achieving Distributed Termination without Freezing. IEEE Trans. Software Eng. 8(3): 287-292(1982) BibTeX
[Francez et al. 1981]
...
[Goldman 1985]
...
[Gouda 1981]
...
[Isloor and Marsland 1980]
...
[Jagannathan and Vasudevan 1982]
...
[Korth et al. 1983]
Henry F. Korth, Ravi Krishnamurthy, Anil Nigam, John T. Robinson: A Framework for Understanding Distributed (Deadlock Detection) Algorithms. PODS 1983: 192-202 BibTeX
[Marsland and Isloor 1980]
...
[Tsai 1982]
...
[Tsai and Beldford 1982]
...
[Wuu and Bernstein 1985]
Gene T. J. Wuu, Arthur J. Bernstein: False Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 11(8): 820-821(1985) BibTeX

Referenced by

  1. 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)
  2. Alexander Thomasian: Distributed Optimistic Concurrency Control Methods for High-Performance Transaction Processing. IEEE Trans. Knowl. Data Eng. 10(1): 173-189(1998)
  3. Jerzy Brzezinski: On Time Complexity of Distributed Algorithms for Generalized Deadlock Detection. ADBIS 1997: 47-55
  4. Kia Makki, Niki Pissinou: Detection and Resolution of Deadlocks in Distributed Database Systems. CIKM 1995: 411-416
  5. Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh: Consistency and Orderability: Semantics-Based Correctness Criteria for Databases. ACM Trans. Database Syst. 18(3): 460-486(1993)
  6. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
  7. Slawomir Pilarski, Tiko Kameda: A Novel Checkpointing Scheme for Distributed Database Systems. PODS 1990: 368-378
  8. ShouHan Wang, Gottfried Vossen: Towards Efficient Algorithms for Deadlock Detection and Resolution in Distributed Systems. ICDE 1989: 287-294
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:54:45 2009