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

@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

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• 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/vldb7588 or /cdrom

• 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

Printed Edition

References

[1]

Edward G. Coffman Jr., M. J. Elphick, Arie Shoshani: System Deadlocks. ACM Comput. Surv. 3(2): 67-78(1971)

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

[3]

Donald S. Fussell, Zvi M. Kedem, Abraham Silberschatz: A Theory of Correct Locking Protocols for Database Systems. VLDB 1981: 112-124

[4]

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

[5]

Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481

[6]

Zvi M. Kedem, Abraham Silberschatz: Controlling Concurrency Using Locking Protocols (Preliminary Report). FOCS 1979: 274-285

[7]

Zvi M. Kedem, Abraham Silberschatz: Locking Protocols: From Exclusive to Shared Locks. J. ACM 30(4): 787-804(1983)

[8]

Zvi M. Kedem, Abraham Silberschatz: Non-Two-Phase Locking Protocols with Shared and Exclusive Locks. VLDB 1980: 309-317

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

[10]

Abraham Silberschatz, Zvi M. Kedem: Consistency in Hierarchical Database Systems. J. ACM 27(1): 72-80(1980)

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

[12]

Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32

[13]

Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung: Locking Policies: Safety and Freedom from Deadlock. FOCS 1979: 286-297