dblp.uni-trier.de www.dagstuhl.de www.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},
  editor    = {Chris Edmondson-Yurkanan and
               Mihalis Yannakakis},
  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, USA},
  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}
}

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 ...

Printed Edition

Chris Edmondson-Yurkanan, Mihalis Yannakakis (Eds.): Proceedings of the Seventh ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 21-23, 1988, Austin, Texas, USA. ACM 1988, ISBN 0-89791-263-2
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

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

References

[1]
Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Philip A. Bernstein, Nathan Goodman, Ming-Yee Lai: Two Part Proof Schema for Database Concurrency Control. Berkeley Workshop 1981: 71-84 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
...
[5]
Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Maurice Herlihy: A Quorum-Consensus Replication Method for Abstract Data Types. ACM Trans. Comput. Syst. 4(1): 32-53(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Maurice Herlihy: Optimistic Concurrency Control for Abstract Data Types. PODC 1986: 206-217 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
...
[9]
Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
...
[13]
...
[14]
David P. Reed: Implementing Atomic Actions on Decentralized Data. ACM Trans. Comput. Syst. 1(1): 3-23(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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

Home | Conferences | Journals | Series | FAQ — Search: Faceted | Free | Complete | Author
Last update Fri May 25 08:32:42 2012 CET by the DBLP Team — This material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page