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.
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
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
- 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)
- 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
- 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