The cost of concurrent, low-contention Read&Modify&Write
Date
2005Source
Structural Information and Communication ComplexityVolume
333Issue
3Pages
373-400Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
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.