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

Hybrid Concurrency Control for Abstract Data Types.

Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. PODS 1988: 201-210
@inproceedings{DBLP:conf/pods/HerlihyW88,
  author    = {Maurice Herlihy and
               William E. Weihl},
  title     = {Hybrid Concurrency Control for Abstract Data Types},
  booktitle = {Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 21-23, 1988, Austin,
               Texas},
  publisher = {ACM},
  year      = {1988},
  isbn      = {0-89791-263-2},
  pages     = {201-210},
  ee        = {http://doi.acm.org/10.1145/308386.308440, db/conf/pods/HerlihyW88.html},
  crossref  = {DBLP:conf/pods/88},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We define a new locking protocol that permits more concurrency than existing commutativity-based protocols. The protocol uses timestamps generated when transactions commit to provide more information about the serialization order of transactions, and hence to weaken the constraints on conflicts. In addition, the protocol permits operations to be both partial and non-deterministic, and it permits results of operations to be used in choosing locks. The protocol exploits type-specific properties of objects, necessary and sufficient constraints on lock conflicts are defned directly from a data type specification. We give a complete formal description of the protocol, encompassing both concurrency control and recovery, and prove that the protocol satisfies hybrid atomicity, a local atomicity property that combines aspects of static and dynamic atomic protocols. We also show that the protocol is optimal in the sense that no hybrid atomic locking scheme can permit more concurrency.

Copyright © 1988 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 Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas. ACM 1988, ISBN 0-89791-263-2
Contents BibTeX

Online Edition: ACM Digital Library

Journal Version

Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. J. Comput. Syst. Sci. 43(1): 25-61(1991) BibTeX

References

[1]
Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX
[2]
Philip A. Bernstein, Nathan Goodman, Ming-Yee Lai: Two Part Proof Schema for Database Concurrency Control. Berkeley Workshop 1981: 71-84 BibTeX
[3]
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
[4]
...
[5]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX
[6]
Maurice Herlihy: A Quorum-Consensus Replication Method for Abstract Data Types. ACM Trans. Comput. Syst. 4(1): 32-53(1986) BibTeX
[7]
Maurice Herlihy: Optimistic Concurrency Control for Abstract Data Types. PODC 1986: 206-217 BibTeX
[8]
...
[9]
Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) BibTeX
[10]
H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX
[11]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX
[12]
...
[13]
...
[14]
David P. Reed: Implementing Atomic Actions on Decentralized Data. ACM Trans. Comput. Syst. 1(1): 3-23(1983) BibTeX
[15]
Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984) BibTeX
[16]
...
[17]
Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX
[18]
...
[19]
William E. Weihl: Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types. ACM Trans. Program. Lang. Syst. 11(2): 249-283(1989) BibTeX
[20]
...

Referenced by

  1. Krithi Ramamritham, Panos K. Chrysanthis: A Taxonomy of Correctness Criteria in Database Applications. VLDB J. 5(1): 85-97(1996)
  2. Man Hon Wong: Recovery for Transaction Failures in Object-Based Databases. PODS 1996: 139-149
  3. Michael Doherty, Richard Hull, Marcia A. Derr, Jacques Durand: On Detecting Conflict Between Proposed Updates. DBPL 1995: 7
  4. Narayanan Krishnakumar, Arthur J. Bernstein: Bounded Ignorance: A Technique for Increasing Concurrency in a Replicated System. ACM Trans. Database Syst. 19(4): 586-625(1994)
  5. Panos K. Chrysanthis, Krithi Ramamritham: Synthesis of Extended Transaction Models Using ACTA. ACM Trans. Database Syst. 19(3): 450-491(1994)
  6. Hans-Jörg Schek, Gerhard Weikum, Haiyan Ye: Towards a Unified Theory of Concurrency Control and Recovery. PODS 1993: 300-311
  7. Andrea H. Skarra: SLEVE: Semantic Locking for EVEnt synchronisation. ICDE 1993: 495-502
  8. Peter Muth, Thomas C. Rakow, Gerhard Weikum, Peter Brössler, Christof Hasse: Semantic Concurrency Control in Object-Oriented Database Systems. ICDE 1993: 233-242
  9. C. Mohan, Donald J. Haderle, Bruce G. Lindsay, Hamid Pirahesh, Peter M. Schwarz: ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. ACM Trans. Database Syst. 17(1): 94-162(1992)
  10. B. R. Badrinath, Krithi Ramamritham: Semantics-Based Concurrency Control: Beyond Commutativity. ACM Trans. Database Syst. 17(1): 163-199(1992)
  11. Man Hon Wong, Divyakant Agrawal: Tolerating Bounded Inconsistency for Increasing Concurrency in Database Systems. PODS 1992: 236-245
  12. Alan Fekete, Nancy A. Lynch, William E. Weihl: Hybrid Atomicity for Nested Transactions. ICDT 1992: 216-230
  13. Naser S. Barghouti, Gail E. Kaiser: Concurrency Control in Advanced Database Applications. ACM Comput. Surv. 23(3): 269-317(1991)
  14. Panos K. Chrysanthis, Krithi Ramamritham: A Formalism for Extended Transaction Model. VLDB 1991: 103-112
  15. Panos K. Chrysanthis, S. Raghuram, Krithi Ramamritham: Extracting Concurrency from Objects: A Methodology. SIGMOD Conference 1991: 108-117
  16. Maurice Herlihy: Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types. ACM Trans. Database Syst. 15(1): 96-124(1990)
  17. Panos K. Chrysanthis, Krithi Ramamritham: ACTA: A Framework for Specifying and Reasoning about Transaction Structure and Behavior. SIGMOD Conference 1990: 194-203
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:54 2009