Commutativity-Based Concurrency Control for Abstract Data Types
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Pagination or Media Count:
This document presents two novel concurrency control algorithms for abstract data types. The algorithms ensure serializability of transactions by using conflict relations based on the commutativity of operations. The author proves that both algorithms ensure a local atomicity property called dynamic atomicity. This means that the algorithms can be used in combination with each other and with other algorithms, as long as the other algorithms also ensure dynamic atomicity. Dynamic atomic concurrency control algorithms include most two-phase locking algorithms, as well as some non-conflict-based algorithms and some optimistic algorithms. The algorithms are quite general, permitting operations be both partial and non-deterministic. In addition, the results returned by operations can be used in determining conflicts, thus permitting higher levels of concurrency than is otherwise possible. In contrast to most their work, our descriptions and proofs encompass recovery as well as concurrency control. Keywords Distributed systems.
- Computer Systems