research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleThe cost of concurrent, low-contention Read&Modify&Write
Bibtex cite IDRACTI-RU1-2005-48
Journal Theoretical Computer Science (TCS)
Year published 2005
Month March
Volume 333
Number 3
Pages 373-400
ISSN 0304-3975
DOI 10.1016/j.tcs.2004.04.018
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.
Busch, Costas
Mavronicolas, Marios
Spirakis, Paul
fulltext.pdf (main file)
Publication ID362