Apologizing Versus Asking Permission: Optimistic Concurrency Control for Abstract Data Types.

@article{DBLP:journals/tods/Herlihy90,
  author    = {Maurice Herlihy},
  title     = {Apologizing Versus Asking Permission: Optimistic Concurrency
               Control for Abstract Data Types},
  journal   = {ACM Trans. Database Syst.},
  volume    = {15},
  number    = {1},
  year      = {1990},
  pages     = {96-124},
  ee        = {http://doi.acm.org/10.1145/77643.77647, db/journals/tods/Herlihy90.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

An optimistic concurrency control technique is one that allows transactions to execute without synchronization, relying on commit-time validation to ensure serializability. Several new optimistic concurrency control techniques for objects in decentralized distributed systems are described here, their correctness and optimality properties are proved, and the circumstances under which each is likely to be useful are characterized.

Unlike many methods that classify operations only as Reads or Writes, these techniques systematically exploit type-specific properties of objects to validate more interleavings. Necessary and sufficient validation conditions can be derived directly from an object's data type specification. These techniques are also modular: they can be applied selectively on a per-object (or even per-operation) basis in conjunction with standard pessimistic techniques such as two-phase locking, permitting optimistic methods to be introduced exactly where they will be most effective.

These techniques can be used to reduce the algorithmic complexity of achieving high levels of concurrency, since certain scheduling decisions that are NP-complete for pessimistic schedulers can be validated after the fact in time, independent of the level of concurrency. These techniques can also enhance the availability of replicated data, circumventing certain tradeoffs between concurrency and availability imposed by comparable pessimistic techniques.

Copyright © 1990 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

• 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

• 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

References

[1]

...

[2]

Divyakant Agrawal, Arthur J. Bernstein, Pankaj Gupta, Soumitra Sengupta: Distributed Optimistic Concurrency Control with Reduced Rollback. Distributed Computing 2(1): 45-59(1987) BibTeX

[3]

Rakesh Agrawal, Michael J. Carey, Miron Livny: Models for Studying Concurrency Control Performance: Alternatives and Implications. SIGMOD Conference 1985: 108-121 BibTeX

[4]

Dushan Z. Badal: Concurrency Control Overhead or Closer Look at Blocking vs. Nonblocking Concurrency Control Mechanisms. Berkeley Workshop 1981: 85-104 BibTeX

[5]

Philip A. Bernstein, Nathan Goodman: The Failure and Recovery Problem for Replicated Databases. PODC 1983: 114-122 BibTeX

[6]

Philip A. Bernstein, Nathan Goodman, Ming-Yee Lai: Two Part Proof Schema for Database Concurrency Control. Berkeley Workshop 1981: 71-84 BibTeX

[7]

Haran Boral, Israel Gold: Towards A Self-Adapting Centralized Concurrency Control Algorithm. SIGMOD Conference 1984: 18-32 BibTeX

[8]

Michael J. Carey: Modeling and Evaluation of Database Concurrency Control Algorithms. Ph.D. thesis, College of Engineering, University of California, Berkeley 1983
BibTeX

[9]

Stefano Ceri, Susan S. Owicki: On the Use of Optimistic Methods for Concurrency Control in Distributed Databases. Berkeley Workshop 1982: 117-129 BibTeX

[10]

Arvola Chan, Stephen Fox, Wen-Te K. Lin, Anil Nori, Daniel R. Ries: The Implementation of an Integrated Concurrency Control and Recovery Scheme. SIGMOD Conference 1982: 184-191 BibTeX

[11]

Deborah DuBourdieux: Implementation of Distributed Transactions. Berkeley Workshop 1982: 81-94 BibTeX

[12]

Cynthia Dwork, Dale Skeen: The Inherent Cost of Nonblocking Commitment. PODC 1983: 1-11 BibTeX

[13]

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

[14]

Peter A. Franaszek, John T. Robinson: Limitations of Concurrency in Transaction Processing. ACM Trans. Database Syst. 10(1): 1-28(1985) BibTeX

[15]

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

[16]

...

[17]

David K. Gifford: Weighted Voting for Replicated Data. SOSP 1979: 150-162 BibTeX

[18]

Jim Gray: Notes on Data Base Operating Systems. Advanced Course: Operating Systems 1978: 393-481 BibTeX

[19]

Theo Härder: Observations on optimistic concurrency control schemes. Inf. Syst. 9(2): 111-120(1984) BibTeX

[20]

Maurice Herlihy: A Quorum-Consensus Replication Method for Abstract Data Types. ACM Trans. Comput. Syst. 4(1): 32-53(1986) BibTeX

[21]

Maurice Herlihy: Concurrency versus Availability: Atomic Mechanisms for Replicated Data. ACM Trans. Comput. Syst. 5(3): 249-274(1987) BibTeX

[22]

Maurice Herlihy: Extending Multiversion Time-Stamping Protocols to Exploit Type Information. IEEE Trans. Computers 36(4): 443-448(1987) BibTeX

[23]

...

[24]

Maurice Herlihy, William E. Weihl: Hybrid Concurrency Control for Abstract Data Types. PODS 1988: 201-210 BibTeX

[25]

...

[26]

Henry F. Korth: Locking Primitives in a Database System. J. ACM 30(1): 55-79(1983) BibTeX

[27]

H. T. Kung, John T. Robinson: On Optimistic Methods for Concurrency Control. ACM Trans. Database Syst. 6(2): 213-226(1981) BibTeX

[28]

Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565(1978) BibTeX

[29]

...

[30]

Georg Lausen: Formal aspects of optimistic concurrency control in a multiple version database system. Inf. Syst. 8(4): 291-301(1983) BibTeX

[31]

Daniel A. Menascé, Tatuo Nakanishi: Optimistic versus pessimistic concurrency control mechanisms in database management systems. Inf. Syst. 7(1): 13-27(1982) BibTeX

[32]

...

[33]

Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX

[34]

David P. Reed: Implementing Atomic Actions on Decentralized Data. ACM Trans. Comput. Syst. 1(1): 3-23(1983) BibTeX

[35]

Manuel Reimer: Solving the Phantom Problem by Predicative Optimistic Concurrency Control. VLDB 1983: 81-88 BibTeX

[36]

Andreas Reuter: Concurrency on High-trafic Data Elements. PODS 1982: 83-92 BibTeX

[37]

Peter M. Schwarz, Alfred Z. Spector: Synchronizing Shared Abstract Types. ACM Trans. Comput. Syst. 2(3): 223-250(1984) BibTeX

[38]

Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988) BibTeX

[39]

Mukul K. Sinha, P. D. Nanadikar, S. L. Mehndiratta: Timestamp Based Certification Schemes for Transactions in Distributed Database Systems. SIGMOD Conference 1985: 402-411 BibTeX

[40]

...

[41]

Robert H. Thomas: A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM Trans. Database Syst. 4(2): 180-209(1979) BibTeX

[42]

William E. Weihl: Commutativity-Based Concurrency Control for Abstract Data Types. IEEE Trans. Computers 37(12): 1488-1505(1988) BibTeX

[43]

William E. Weihl: Local Atomicity Properties: Modular Concurrency Control for Abstract Data Types. ACM Trans. Program. Lang. Syst. 11(2): 249-283(1989) BibTeX

[44]

...

Referenced by

1. Arthur J. Bernstein, David Scott Gerstl, Wai-Hong Leung, Philip M. Lewis: Design and Performance of an Assertional Concurrency Control System. ICDE 1998: 436-445
2. Dimitrios Georgakopoulos, Mark F. Hornick, Frank Manola: Customizing Transaction Models and Mechanisms in a Programmable Environment Supporting Reliable Workflow Automation. IEEE Trans. Knowl. Data Eng. 8(4): 630-649(1996)
3. Dimitrios Georgakopoulos, Marek Rusinkiewicz, Witold Litwin: Chronological Scheduling of Transactions with Temporal Dependencies. VLDB J. 3(1): 1-28(1994)
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. Dimitrios Georgakopoulos, Mark F. Hornick, Piotr Krychniak, Frank Manola: Specification and Management of Extended Transactions in a Programmable Transaction Environment. ICDE 1994: 462-473
6. Rajeev Rastogi, Sharad Mehrotra, Yuri Breitbart, Henry F. Korth, Abraham Silberschatz: On Correctness of Non-serializable Executions. PODS 1993: 97-108
7. Rajeev Rastogi, Henry F. Korth, Abraham Silberschatz: Strict Histories in Object-Based Database Systems. PODS 1993: 288-299
8. B. R. Badrinath, Krithi Ramamritham: Semantics-Based Concurrency Control: Beyond Commutativity. ACM Trans. Database Syst. 17(1): 163-199(1992)