Abstract | This work addresses the possibility or impossibility,and the corresponding costs,of devising
concurrent, low-contention implementations of atomicRead&Modify&Write (orRMW) operations
in a distributed system. A natural class of monotone RMW operations associated with monotone
groups,a certain class of algebraic groups introduced here,is considered. The popular Fetch&Add
and Fetch&Multiply operations are examples from the class.
A Monotone Linearizability Lemma is proved and employed as a chief combinatorial instrument in
this work; it establishes inherent ordering constraints of linearizability for a certain class of executions
of any distributed system implementing a monotone RMW operation. |