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

Deadlock Resolution and Semantic Lock Models in Object-Oriented Distributed Systems.

Marina Roesler, Walter A. Burkhard: Deadlock Resolution and Semantic Lock Models in Object-Oriented Distributed Systems. SIGMOD Conference 1988: 361-370
@inproceedings{DBLP:conf/sigmod/RoeslerB88,
  author    = {Marina Roesler and
               Walter A. Burkhard},
  editor    = {Haran Boral and
               Per-{\AA}ke Larson},
  title     = {Deadlock Resolution and Semantic Lock Models in Object-Oriented
               Distributed Systems},
  booktitle = {Proceedings of the 1988 ACM SIGMOD International Conference on
               Management of Data, Chicago, Illinois, June 1-3, 1988},
  publisher = {ACM Press},
  year      = {1988},
  pages     = {361-370},
  ee        = {http://doi.acm.org/10.1145/50202.50246, db/conf/sigmod/RoeslerB88.html},
  crossref  = {DBLP:conf/sigmod/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We propose a distributed algorithm for detection and resolution of resource deadlocks in object-oriented distributed systems. The algorithm porposed is shown to detect and resolve all O(n1) cycles present in the worst case waits-for-graph (WFG) with n vertices by transmitting O(n3) messages of small constant size. Its average time complexity has been shown to be O(ne), where e is the number of edges in the WFG. After deadlock resolution, the algorithm leaves information in the system concerning dependence relations of running transactions. This information will preclude the wasteful retransmission of messages and reduce the delay in detecting future deadlocks.

Copyright © 1988 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

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Haran Boral, Per-Åke Larson (Eds.): Proceedings of the 1988 ACM SIGMOD International Conference on Management of Data, Chicago, Illinois, June 1-3, 1988. ACM Press 1988 BibTeX , SIGMOD Record 17(2), June 1988
Contents

Online Edition: ACM Digital Library


References

[BBG88]
Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A model for concurrency in nested transactions systems. J. ACM 36(2): 230-269(1989) BibTeX
[BT87]
Gabriel Bracha, Sam Toueg: Distributed Deadlock Detection. Distributed Computing 2(3): 127-138(1987) BibTeX
[CKST87]
...
[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
[Elm86]
Ahmed K. Elmagarmid: A Survey of Distributed Deadlock Algorithms. SIGMOD Record 15(3): 37-45(1986) BibTeX
[Gra78]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[GS80]
Virgil D. Gligor, Susan H. Shattuck: On Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 6(5): 435-440(1980) BibTeX
[HM83]
...
[Kor83]
Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) 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
[Mos81]
...
[Obe82]
Ron Obermarck: Distributed Deadlock Detection Algorithm. ACM Trans. Database Syst. 7(2): 187-208(1982) BibTeX
[RB87]
...
[RBC87]
Marina Roesler, Walter A. Burkhard, Kenneth B. Cooper: Efficient Deadlock Resolution for Lock-Based Concurrency Control Schemes. ICDCS 1988: 224-233 BibTeX
[Sch84]
...
[SN85]
Mukul K. Sinha, N. Natarajan: A Priority Based Distributed Deadlock Detection Algorithm. IEEE Trans. Software Eng. 11(1): 67-80(1985) BibTeX
[Wei84]
...

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. Young Chul Park, Peter Scheuermann, Hsiang-Lung Tung: A Distributed Deadlock Detection and Resolution Algorithm Based on A Hybrid Wait-for Graph and Probe Generation Scheme. CIKM 1995: 378-386
  3. 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:39:55 2009