Theory of Serializability for a Parallel Model of Transactions.
Ravi Krishnamurthy, Umeshwar Dayal:
Theory of Serializability for a Parallel Model of Transactions.
PODS 1982: 293-305@inproceedings{DBLP:conf/pods/KrishnamurthyD82,
author = {Ravi Krishnamurthy and
Umeshwar Dayal},
title = {Theory of Serializability for a Parallel Model of Transactions},
booktitle = {Proceedings of the ACM Symposium on Principles of Database Systems,
March 29-31, 1982, Los Angeles, California},
publisher = {ACM},
year = {1982},
pages = {293-305},
ee = {http://doi.acm.org/10.1145/588111.588158, db/conf/pods/KrishnamurthyD82.html},
crossref = {DBLP:conf/pods/82},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
In this paper we present a parallel program
schema model of a transaction system and
generalize the concept of serializability from the
sequential two-step model to a parallel multi-step
model. We define two classes of serializable executions,
and for each class we discuss two problems:
recognition and scheduling. It is shown that the
results for the recognition and online scheduling
problems for the sequential model generalize to the
parallel model. But it is argued that online scheduling
is not suitable for a parallel execution environment.
Therefore, batch schedulers are defined and
a minimal set of precedence constraints is derived.
Finally, it is shown that any optimal batch scheduler
that uses syntactic information alone cannot be efficient.
Copyright © 1982 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 ...
Printed Edition
Proceedings of the ACM Symposium on Principles of Database Systems, March 29-31, 1982, Los Angeles, California.
ACM 1982
Contents 
References
- [BSR80]
- Philip A. Bernstein, David W. Shipman, James B. Rothnie Jr.:
Concurrency Control in a System for Distributed Databases (SDD-1).
ACM Trans. Database Syst. 5(1): 18-51(1980)
- [BSW79]
- Philip A. Bernstein, David W. Shipman, Wing S. Wong:
Formal Aspects of Serializability in Database Concurrency Control.
IEEE Trans. Software Eng. 5(3): 203-216(1979)
- [DeW78]
- ...
- [EGLT76]
- 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)
- [G66]
- ...
- [G69]
- Ronald L. Graham:
Bounds on Multiprocessing Timing Anomalies.
SIAM Journal of Applied Mathematics 17(2): 416-429(1969)
- [GJ80]
- 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
- [Gou80]
- ...
- [KD81]
- Ravi Krishnamurthy, Umeshwar Dayal:
On the Correct and Efficient Scheduling of Transactions in a Highly Parallel Database Machine.
Berkeley Workshop 1982: 329-361
- [Kell73]
- Robert M. Keller:
Parallel Program Schemata and Maximal Parallelism II: Construction of Closures.
J. ACM 20(4): 696-710(1973)
- [KP79]
- H. T. Kung, Christos H. Papadimitriou:
An Optimality Theory of Concurrency Control for Databases.
SIGMOD Conference 1979: 116-126
- [KP81]
- Paris C. Kanellakis, Christos H. Papadimitriou:
The Complexity of Distributed Concurrency Control.
FOCS 1981: 185-197
- [Kris82]
- ...
- [Papa79]
- Christos H. Papadimitriou:
The serializability of concurrent database updates.
J. ACM 26(4): 631-653(1979)
- [PBR77]
- ...
- [Wilh76]
- Neil C. Wilhelm:
An Anomaly in Disk Scheduling: A Comparison of FCFS and SSTF Seek Scheduling Using an Empirical Model for Disk Accesses.
Commun. ACM 19(1): 13-17(1976)
- [Ull75]
- Jeffrey D. Ullman:
NP-Complete Scheduling Problems.
J. Comput. Syst. Sci. 10(3): 384-393(1975)
Copyright © Mon Mar 15 03:51:31 2010
by Michael Ley (ley@uni-trier.de)
