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},
crossref = {DBLP:conf/sigmod/88},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
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 ...
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 
, 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)
- [BT87]
- Gabriel Bracha, Sam Toueg:
Distributed Deadlock Detection.
Distributed Computing 2(3): 127-138(1987)
- [CKST87]
- ...
- [CM82]
- K. Mani Chandy, Jayadev Misra:
A Distributed Algorithm for Detecting Resource Deadlocks in Distributed Systems.
PODC 1982: 157-164
- [CMH83]
- K. Mani Chandy, Jayadev Misra, Laura M. Haas:
Distributed Deadlock Detection.
ACM Trans. Comput. Syst. 1(2): 144-156(1983)
- [Elm86]
- Ahmed K. Elmagarmid:
A Survey of Distributed Deadlock Algorithms.
SIGMOD Record 15(3): 37-45(1986)
- [Gra78]
- Jim Gray:
Notes on Data Base Operating Systems.
Advanced Course: Operating Systems 1978: 393-481
- [GS80]
- Virgil D. Gligor, Susan H. Shattuck:
On Deadlock Detection in Distributed Systems.
IEEE Trans. Software Eng. 6(5): 435-440(1980)
- [HM83]
- ...
- [Kor83]
- Henry F. Korth:
Locking Primitives in a Database System.
J. ACM 30(1): 55-79(1983)
- [MM79]
- Daniel A. Menascé, Richard R. Muntz:
Locking and Deadlock Detection in Distributed Data Bases.
IEEE Trans. Software Eng. 5(3): 195-202(1979)
- [Mos81]
- ...
- [Obe82]
- Ron Obermarck:
Distributed Deadlock Detection Algorithm.
ACM Trans. Database Syst. 7(2): 187-208(1982)
- [RB87]
- ...
- [RBC87]
- Marina Roesler, Walter A. Burkhard, Kenneth B. Cooper:
Efficient Deadlock Resolution for Lock-Based Concurrency Control Schemes.
ICDCS 1988: 224-233
- [Sch84]
- ...
- [SN85]
- Mukul K. Sinha, N. Natarajan:
A Priority Based Distributed Deadlock Detection Algorithm.
IEEE Trans. Software Eng. 11(1): 67-80(1985)
- [Wei84]
- ...
Last update Tue Sep 18 00:25:02 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
