Cautious Transaction Schedulers with Admission Control.

Naoki Katoh, Toshihide Ibaraki, Tiko Kameda: Cautious Transaction Schedulers with Admission Control. ACM Trans. Database Syst. 10(2): 205-229(1985)

@article{DBLP:journals/tods/KatohIK85,
  author    = {Naoki Katoh and
               Toshihide Ibaraki and
               Tiko Kameda},
  title     = {Cautious Transaction Schedulers with Admission Control},
  journal   = {ACM Trans. Database Syst.},
  volume    = {10},
  number    = {2},
  year      = {1985},
  pages     = {205-229},
  ee        = {http://doi.acm.org/10.1145/3857.3860, db/journals/tods/KatohIK85.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

We propose a new class of schedulers, called cautious schedulers, that grant an input request if it will not necessitate any rollback in the future. In particular, we investigate cautious WRW-schedulers that output schedules in class WRW only. Class WRW consists of all schedules that are serializable, while preserving the write-read and read-write conflict, and is the largest polynomially recognizable subclass of serializable schedules currently known. It is shown, in this paper however, that cautious WRW-scheduling is, in general, NP-complete. Therefore, we introduce a special type (type 1R) of transaction, which consists of no more than one read step (an indivisible set of read operations) followed by multiple write steps. It is shown that cautious WRW-scheduling can be performed efficiently if all transactions are of type 1R and if admission control can be exercised. Admission control rejects a transaction unless its first request is immediately grantable.

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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ...

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/An3-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

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/aDVD2 or /dvd

BibTeX

References

[1]: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX
[2]: 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) BibTeX
[3]: Gael N. Buckley, Abraham Silberschatz: Obtaining Progressive Protocols for a Simple Multiversion Database Model. VLDB 1983: 74-80 BibTeX
[4]: Michael J. Carey, Michael Stonebraker: The Performance of Concurrency Control Algorithms for Database Management Systems. VLDB 1984: 107-118 BibTeX
[5]: Marco A. Casanova, Philip A. Bernstein: General Purpose Schedulers for Database Systems. Acta Inf. 14: 195-220(1980) BibTeX
[6]: ...
[7]: 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
[8]: 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
[9]: ...
[10]: Toshihide Ibaraki, Tiko Kameda, Toshimi Minoura: Disjoint-Interval Topological Sort: A Useful Concept in Serializability Theory (Extended Abstract). VLDB 1983: 89-91 BibTeX
[11]: ...
[12]: Naoki Katoh, Tiko Kameda, Toshihide Ibaraki: A Cautious Scheduler for Multistep Transactions. Algorithmica 2: 1-26(1987) BibTeX
[13]: ...
[14]: H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX
[15]: Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX
[16]: Ravi Sethi: A model of concurrent database transactions (summary). FOCS 1981: 175-184 BibTeX
[17]: Ravi Sethi: Useless Actions Make a Difference: Strict Serializability of Database Updates. J. ACM 29(2): 394-403(1982) BibTeX
[18]: Richard Edwin Stearns, Philip M. Lewis II, Daniel J. Rosenkrantz: Concurrency Control for Database Systems. FOCS 1976: 19-32 BibTeX

Referenced by

P. Krishna Reddy, Subhash Bhalla: A Nonblocking Transaction Data Flow Graph Based Protocol For Replicated Databases. IEEE Trans. Knowl. Data Eng. 7(5): 829-834(1995)
Georg Lausen, Eljas Soisalon-Soininen: Locling Policies and Predeclared Transactions. MFDBS 1989: 317-336
Toshihide Ibaraki, Tiko Kameda, Toshimi Minoura: Serializability with Constraints. ACM Trans. Database Syst. 12(3): 429-452(1987)

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]