wtwolfe@hubcap.clemson.edu (Bill Wolfe) (09/10/89)
The following article can be found in the April 1989 issue of
ACM Transactions on Programming Languages and Systems:
Local Atomicity Properties: Modular Concurrency Control
for Abstract Data Types (Author: William E. Weihl, of MIT)
Atomic actions (or transactions) are useful for coping with
concurrency and failures. One way of ensuring atomicity of
actions is to implement applications in terms of _atomic data
types_: abstract data types whose objects ensure serializability
and recoverability of actions using them. Many atomic types can
be implemented to provide high levels of concurrency by taking
advantage of algebraic properties of the type's operations, for
example, that certain operations commute. In this paper we analyze
the level of concurrency permitted by an atomic type. We introduce
several local constraints on individual objects that suffice to ensure
global atomicity of actions; we call these constraints _local atomicity
properties_. We present three local atomicity properties, each of
which is _optimal_: no strictly weaker local constraint suffices to
ensure global atomicity for actions. Thus, the local atomicity
properties define precise limits on the amount of concurrency that
can be permitted by an atomic type.
Bill Wolfe, wtwolfe@hubcap.clemson.edu