ACM SIGMOD Anthology VLDB dblp.uni-trier.de

An Efficient Deadlock Removal Scheme for Non-Two-Phase Locking Protocols.

Zvi M. Kedem, C. Mohan, Abraham Silberschatz: An Efficient Deadlock Removal Scheme for Non-Two-Phase Locking Protocols. VLDB 1982: 91-97
@inproceedings{DBLP:conf/vldb/KedemMS82,
  author    = {Zvi M. Kedem and
               C. Mohan and
               Abraham Silberschatz},
  title     = {An Efficient Deadlock Removal Scheme for Non-Two-Phase Locking
               Protocols},
  booktitle = {Eigth International Conference on Very Large Data Bases, September
               8-10, 1982, Mexico City, Mexico, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1982},
  isbn      = {0-934613-14-1},
  pages     = {91-97},
  ee        = {db/conf/vldb/KedemMS82.html},
  crossref  = {DBLP:conf/vldb/82},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Over the years several locking protocols have been proposed for coordinating the concurrent use of a data base by multiple transactions. Of these, the non-two-phase locking (non-2PL) protocols form a large class. The Pitfall Protocol (PP) is one of the non-2PL protocols. While the rules of PP assure serializability, they do not prevent deadlocks from occurring. Resolution of a deadlock by partially/fully undoing (i.e. rolling back) the actions of one of the transactions involved in the deadlock may result in two undesirable consequences: a) cascading rollbacks -- more than one transaction may have to be rolled back, b) rollback of completed transaction -- a transaction that has terminated could be required to be rolled back. Thus a complex commit protocol may be necessary to determine whether a transaction may be allowed to commit.

It is the goal of this paper to introduce a simple additional condition to the rules of PP that will allow very simple handling of deadlocks by partial rollbacks, without causing the above undesirable effects.

Copyright © 1982 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.


Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Eigth International Conference on Very Large Data Bases, September 8-10, 1982, Mexico City, Mexico, Proceedings. Morgan Kaufmann 1982, ISBN 0-934613-14-1
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Edward G. Coffman Jr., M. J. Elphick, Arie Shoshani: System Deadlocks. ACM Comput. Surv. 3(2): 67-78(1971) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Donald S. Fussell, Zvi M. Kedem, Abraham Silberschatz: A Theory of Correct Locking Protocols for Database Systems. VLDB 1981: 112-124 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Donald S. Fussell, Zvi M. Kedem, Abraham Silberschatz: Deadlock Removal Using Partial Rollback in Database Systems. SIGMOD Conference 1981: 65-73 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
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
[6]
Zvi M. Kedem, Abraham Silberschatz: Controlling Concurrency Using Locking Protocols (Preliminary Report). FOCS 1979: 274-285 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Zvi M. Kedem, Abraham Silberschatz: Locking Protocols: From Exclusive to Shared Locks. J. ACM 30(4): 787-804(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
Zvi M. Kedem, Abraham Silberschatz: Non-Two-Phase Locking Protocols with Shared and Exclusive Locks. VLDB 1980: 309-317 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[9]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Abraham Silberschatz, Zvi M. Kedem: A Family of Locking Protocols for Database Systems that Are Modeled by Directed Graphs. IEEE Trans. Software Eng. 8(6): 558-562(1982) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung: Locking Policies: Safety and Freedom from Deadlock. FOCS 1979: 286-297 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:57 2010 by Michael Ley (ley@uni-trier.de)