dblp.uni-trier.de www.dagstuhl.de www.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},
  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.


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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, 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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BT87]
Gabriel Bracha, Sam Toueg: Distributed Deadlock Detection. Distributed Computing 2(3): 127-138(1987) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CKST87]
...
[CM82]
K. Mani Chandy, Jayadev Misra: A Distributed Algorithm for Detecting Resource Deadlocks in Distributed Systems. PODC 1982: 157-164 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[CMH83]
K. Mani Chandy, Jayadev Misra, Laura M. Haas: Distributed Deadlock Detection. ACM Trans. Comput. Syst. 1(2): 144-156(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Elm86]
Ahmed K. Elmagarmid: A Survey of Distributed Deadlock Algorithms. SIGMOD Record 15(3): 37-45(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gra78]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[GS80]
Virgil D. Gligor, Susan H. Shattuck: On Deadlock Detection in Distributed Systems. IEEE Trans. Software Eng. 6(5): 435-440(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HM83]
...
[Kor83]
Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MM79]
Daniel A. Menascé, Richard R. Muntz: Locking and Deadlock Detection in Distributed Data Bases. IEEE Trans. Software Eng. 5(3): 195-202(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mos81]
...
[Obe82]
Ron Obermarck: Distributed Deadlock Detection Algorithm. ACM Trans. Database Syst. 7(2): 187-208(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RB87]
...
[RBC87]
Marina Roesler, Walter A. Burkhard, Kenneth B. Cooper: Efficient Deadlock Resolution for Lock-Based Concurrency Control Schemes. ICDCS 1988: 224-233 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Sch84]
...
[SN85]
Mukul K. Sinha, N. Natarajan: A Priority Based Distributed Deadlock Detection Algorithm. IEEE Trans. Software Eng. 11(1): 67-80(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wei84]
...

Last update Tue Sep 18 00:25:02 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page