Hybrid Concurrency Control for Abstract Data Types
Abstract
Atomic transactions are a widely accepted mechanism for coping with failures and concurrency in database systems, both distributed and centralized. Many algorithms have been proposed for concurrency control and recovery. Recent work has focused on typed objects, such as queues, directories, or counters, that provide a richer set of operations. Several algorithms have been proposed to enhance concurrency and recovery by exploiting data objects' type-specific properties. Most of these algorithms are locking schemes in which conflicts are governed by some notion of commutativity: lock modes for commuting operations do not conflict. This paper presents a new locking algorithm that permits more concurrency than existing commutativity-based protocols. In addition, the protocol permits operations to be both partial and non-deterministic, and it permits the lock mode for an operation to be determined by its results as well as its name and arguments. The protocol exploits type-specific properties of objects; necessary and sufficient constraints on lock conflicts are defined 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. Keywords: Distributed data processing, Locking, Time stamps, Local atomicity, Hybrid atomicity.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1988
- Accession Number
- ADA200981
Entities
People
- Maurice P. Herlihy
- William E. Weihl
Organizations
- Massachusetts Institute of Technology