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

A Framework for Understanding Distributed (Deadlock Detection) Algorithms.

Henry F. Korth, Ravi Krishnamurthy, Anil Nigam, John T. Robinson: A Framework for Understanding Distributed (Deadlock Detection) Algorithms. PODS 1983: 192-202
@inproceedings{DBLP:conf/pods/KorthKNR83,
  author    = {Henry F. Korth and
               Ravi Krishnamurthy and
               Anil Nigam and
               John T. Robinson},
  title     = {A Framework for Understanding Distributed (Deadlock Detection)
               Algorithms},
  booktitle = {Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles
               of Database Systems, March 21-23, 1983, Colony Square Hotel,
               Atlanta, Georgia},
  publisher = {ACM},
  year      = {1983},
  isbn      = {0-89791-097-4},
  pages     = {192-202},
  ee        = {http://doi.acm.org/10.1145/588058.588082, db/conf/pods/KorthKNR83.html},
  crossref  = {DBLP:conf/pods/83},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Distributed algorithms tend to be difficult to understand and even more difficult to prove correct. Using distributed deadlock detection as a running example this paper presents a framework for stating, understanding, and proving the correctness of distributed algorithms for decision problems. The framework consists of a series of complexity levels. To simplify the initial levels, we treat the data structure of the algorithm as a database, and use the database notions of views and transaction atomicity. For each complexity level, we state theorems that need to be proved for each algorithm. The framework is illustrated using several existing deadlock detection algorithms. Finally, it is shown that the framework suggests new algorithms using the best features of several existing algorithms.

Copyright © 1983 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 21-23, 1983, Colony Square Hotel, Atlanta, Georgia. ACM 1983, ISBN 0-89791-097-4
Contents BibTeX

Online Edition: ACM Digital Library

References

[Beeri, Obermarck 1981]
Catriel Beeri, Ron Obermarck: A Resource Class Independent Deadlock Detection Algorithm. VLDB 1981: 166-178 BibTeX
[Bernstein, Goodman 1981]
Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX
[Bernstein, Goodman 1982]
Arthur J. Bernstein, Nathan Goodman: Concurrency Control Algorithms for Multiversion Database Systems. PODC 1982: 209-215 BibTeX
[Chandra et al. 1974]
...
[Chandy, Misra 1982]
K. Mani Chandy, Jayadev Misra: A Distributed Algorithm for Detecting Resource Deadlocks in Distributed Systems. PODC 1982: 157-164 BibTeX
[Chang 1979]
...
[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 1978]
...
[Dijkstra, Scholten 1980]
Edsger W. Dijkstra, Carel S. Scholten: Termination Detection for Diffusing Computations. Inf. Process. Lett. 11(1): 1-4(1980) BibTeX
[Gligor, Shattuck 1980]
Virgil D. Gligor, Susan H. Shattuck: On Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 6(5): 435-440(1980) BibTeX
[Goldman 1977]
...
[Ho, Ramamoorthy 1982]
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
[Isloor, Marsland 1978]
...
[Isloor, Marsland 1980]
...
[Lamport 1978]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX
[Marsland, Isloor 1980]
...
[Menasce, 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
[Mohan 1980]
...
[Obermarck 1982]
Ron Obermarck: Distributed Deadlock Detection Algorithm. ACM Trans. Database Syst. 7(2): 187-208(1982) BibTeX
[Tsai 1982]
...

Referenced by

  1. Yuri Breitbart, Henry F. Korth: Replication and Consistency: Being Lazy Helps Sometimes. PODS 1997: 173-184
  2. Edgar Knapp: Deadlock Detection in Distributed Databases. ACM Comput. Surv. 19(4): 303-328(1987)
  3. Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
    Contents
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:33:42 2009