The cost of concurrent, low-contention Read&Modify&Write

Abstract

The possibility or impossibility and the corresponding costs of devising concurrent, low-contention implementations of atomic Read&Modify&Write (or RMW) operations in a distributed system were addressed. A natural class of monotone RMW operations associated with monotone groups was introduced. A certain class of algebraic groups was also presented. A Monotone Linearizability Lemma was proved and employed as a chief combinatorial instrument. It establishes inherent ordering constraints of linearizability for a certain class of executions of any distributed system implementing a monotone RMW operation. A lower bound on latency for switching networks that implement monotone groups was proved by using Monotone Linearizability Lemma.