ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library


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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[G66]
...
[G69]
Ronald L. Graham: Bounds on Multiprocessing Timing Anomalies. SIAM Journal of Applied Mathematics 17(2): 416-429(1969) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kell73]
Robert M. Keller: Parallel Program Schemata and Maximal Parallelism II: Construction of Closures. J. ACM 20(4): 696-710(1973) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KP79]
H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. SIGMOD Conference 1979: 116-126 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[KP81]
Paris C. Kanellakis, Christos H. Papadimitriou: The Complexity of Distributed Concurrency Control. FOCS 1981: 185-197 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Kris82]
...
[Papa79]
Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ull75]
Jeffrey D. Ullman: NP-Complete Scheduling Problems. J. Comput. Syst. Sci. 10(3): 384-393(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Mon Mar 15 03:51:31 2010 by Michael Ley (ley@uni-trier.de)