🚀 go-pugleaf

   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