Commutativity-Based Concurrency Control for Abstract Data Types

Abstract

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1988
Accession Number
ADA200979

Entities

People

  • William E. Weihl

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Automata
  • Classification
  • Computations
  • Computer Science
  • Control Systems
  • Determinants (Mathematics)
  • Equations
  • Guarantees
  • Language
  • Machines
  • Multithreading
  • Recovery
  • Security
  • Sequences
  • Specifications

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Parallel and Distributed Computing.