Deadlock Removal Using Partial Rollback in Database Systems.

Donald S. Fussell, Zvi M. Kedem, Abraham Silberschatz: Deadlock Removal Using Partial Rollback in Database Systems. SIGMOD Conference 1981: 65-73

@inproceedings{DBLP:conf/sigmod/KedemS81,
  author    = {Donald S. Fussell and
               Zvi M. Kedem and
               Abraham Silberschatz},
  editor    = {Y. Edmund Lien},
  title     = {Deadlock Removal Using Partial Rollback in Database Systems},
  booktitle = {Proceedings of the 1981 ACM SIGMOD International Conference on
               Management of Data, Ann Arbor, Michigan, April 29 - May 1, 1981},
  publisher = {ACM Press},
  year      = {1981},
  pages     = {65-73},
  ee        = {http://doi.acm.org/10.1145/582318.582329, db/conf/sigmod/KedemS81.html},
  crossref  = {DBLP:conf/sigmod/81},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

The problem of removing deadlocks from concurrent database systems using the two-phase locking protocol is considered. In particular, for systems which use no a priori information about transaction behavior in order to avoid deadlocks, it has generally been assumed necessary to totally remove and restart some transaction involved in a deadlock in order to relieve the situation. In this paper, a new approach to deadlock removal in such systems based on partial rollbacks is introduced. This approach does not in general require the total removal of a transaction to eliminate a deadlock. The task of optimizing deadlock removal using this method is discussed for systems allowing both exclusive and shared locking. A method is given for implementing this approach with no more storage overhead than that required for total removal and restart.

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod7592 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

BibTeX

Printed Edition

Y. Edmund Lien (Ed.): Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, Ann Arbor, Michigan, April 29 - May 1, 1981. ACM Press 1981 BibTeX
Contents

Online Edition: ACM Digital Library

References

[1]: ...
[2]: Edward G. Coffman Jr., M. J. Elphick, Arie Shoshani: System Deadlocks. ACM Comput. Surv. 3(2): 67-78(1971) BibTeX
[3]: ...
[4]: Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX
[5]: Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[6]: Zvi M. Kedem, Abraham Silberschatz: Controlling Concurrency Using Locking Protocols (Preliminary Report). FOCS 1979: 274-285 BibTeX
[7]: Daniel J. Rosenkrantz, Richard Edwin Stearns, Philip M. Lewis II: System Level Concurrency Control for Distributed Database Systems. ACM Trans. Database Syst. 3(2): 178-198(1978) BibTeX
[8]: ...
[9]: Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) BibTeX
[10]: Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX

Referenced by

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents
Zvi M. Kedem, C. Mohan, Abraham Silberschatz: An Efficient Deadlock Removal Scheme for Non-Two-Phase Locking Protocols. VLDB 1982: 91-97
C. Mohan, Donald S. Fussell, Abraham Silberschatz: Compatibility and Commutativity in Non-two-phase Locking Protocols. PODS 1982: 283-292
Vassos Hadzilacos: An Algorithm for Minimizing Roll Back Cost. PODS 1982: 93-97

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]