Deadlock-Freedom (and Safety) of Transactions in a Distributed Database.
Ouri Wolfson, Mihalis Yannakakis:
Deadlock-Freedom (and Safety) of Transactions in a Distributed Database.
PODS 1985: 105-112@inproceedings{DBLP:conf/pods/WolfsonY85,
author = {Ouri Wolfson and
Mihalis Yannakakis},
title = {Deadlock-Freedom (and Safety) of Transactions in a Distributed
Database},
booktitle = {Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles
of Database Systems, March 25-27, 1985, Portland, Oregon},
publisher = {ACM},
year = {1985},
isbn = {0-89791-153-9},
pages = {105-112},
ee = {http://doi.acm.org/10.1145/325405.325418, db/conf/pods/WolfsonY85.html},
crossref = {DBLP:conf/pods/85},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
We analyze the problem of determining freedom
from deadlock of transactions which control concurrency
by locking in a distributed database. In practice the
problem is important, for example, in deciding whether the
deadlock-detection-and-elimiaation mechanism of a
Distributed Database Management System can be turned
off (to reduce overhead). We use a graph-theoretic
formalization of the problem and show that it is coNP-complete
even for two transactions (although polynomial in
this case for a centralized database). If the number of
database sites is fixed, we outline a polynomial-time
algorithm. The problem of determining safety
(serializability of all schedules) and deadlock freedom is
also examined. We show that it is polynomial for a fixed
number of transactions (and a variable number of database sites).
Copyright © 1985 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.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
BibTeX
Printed Edition
Proceedings of the Fourth ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March 25-27, 1985, Portland, Oregon.
ACM 1985, ISBN 0-89791-153-9
Contents BibTeX
Journal Version
Ouri Wolfson, Mihalis Yannakakis:
Deadlock-Freedom (and Safety) of Transactions in a Distributed Database.
J. Comput. Syst. Sci. 33(2): 161-178(1986) BibTeX
References
- [BG]
- Philip A. Bernstein, Nathan Goodman:
Concurrency Control in Distributed Database Systems.
ACM Comput. Surv. 13(2): 185-221(1981) BibTeX
- [EGLT]
- 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
- [FKS]
- Donald S. Fussell, Zvi M. Kedem, Abraham Silberschatz:
A Theory of Correct Locking Protocols for Database Systems.
VLDB 1981: 112-124 BibTeX
- [GJ]
- M. R. Garey, David S. Johnson:
Computers and Intractability: A Guide to the Theory of NP-Completeness.
W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
- [J]
- ...
- [KP1]
- Paris C. Kanellakis, Christos H. Papadimitriou:
The Complexity of Distributed Concurrency Control.
FOCS 1981: 185-197 BibTeX
- [KP2]
- Paris C. Kanellakis, Christos H. Papadimitriou:
Is Distributed Locking Harder?
PODS 1982: 98-107 BibTeX
- [LP]
- Witold Lipski Jr., Christos H. Papadimitriou:
A Fast Algorithm for Testing for Safety and Detecting Deadlocks in Locked Transaction Systems.
J. Algorithms 2(3): 211-226(1981) BibTeX
- [LW]
- Y. Edmund Lien, Peter J. Weinberger:
Consistency, Concurrency and Crash Recovery.
SIGMOD Conference 1978: 9-14 BibTeX
- [P1]
- Christos H. Papadimitriou:
Concurrency Control by Locking.
SIAM J. Comput. 12(2): 215-226(1983) BibTeX
- [P2]
- Christos H. Papadimitriou:
The serializability of concurrent database updates.
J. ACM 26(4): 631-653(1979) BibTeX
- [RSL]
- 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
- [SK]
- Abraham Silberschatz, Zvi M. Kedem:
Consistency in Hierarchical Database Systems.
J. ACM 27(1): 72-80(1980) BibTeX
- [SW]
- Eljas Soisalon-Soininen, Derick Wood:
Optimal Algorithms to Compute the Closure of a Set of Iso-Rectangles.
J. Algorithms 5(2): 199-214(1984) BibTeX
- [T]
- Henry Tirri:
Freedom from Deadlock of Locked Transactions in a Distributed Database.
PODC 1983: 267-276 BibTeX
- [U]
- ...
- [W1]
- ...
- [W2]
- Ouri Wolfson:
An Algorithm for Early Unlocking of Entities in Database Transactions.
J. Algorithms 7(1): 146-156(1986) BibTeX
- [Y1]
- Mihalis Yannakakis:
A Theory of Safe Locking Policies in Database Systems.
J. ACM 29(3): 718-740(1982) BibTeX
- [Y2]
- Mihalis Yannakakis:
Freedom from Deadlock of Safe Locking Policies.
SIAM J. Comput. 11(2): 391-408(1982) BibTeX
- [YPK]
- Mihalis Yannakakis, Christos H. Papadimitriou, H. T. Kung:
Locking Policies: Safety and Freedom from Deadlock.
FOCS 1979: 286-297 BibTeX
Referenced by
- Jeffrey D. Ullman:
Principles of Database and Knowledge-Base Systems, Volume II.
Computer Science Press 1989, ISBN 0-7167-8162-X
Contents - Ouri Wolfson:
The Overhead of Locking (and Commit) Protocols in Distributed Databases.
ACM Trans. Database Syst. 12(3): 453-471(1987)
- Ouri Wolfson:
The Performance of Locking Protocols in Distributed Databases.
ICDE 1987: 259-266
- Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman:
Concurrency Control and Recovery in Database Systems.
Addison-Wesley 1987, ISBN 0-201-10715-5
Contents - Ouri Wolfson:
A New Characterization of Distributed Deadlock in Databases.
ICDT 1986: 436-444
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:47 2009