TY - JOUR
T1 - The cost of concurrent, low-contention Read&Modify&Write
AU - Busch, Costas
AU - Mavronicolas, Marios
AU - Spirakis, Paul
N1 - Funding Information:
A preliminary version of this work appears in the Proceedings of the 10th International Colloquium on Structural Information and Communication Complexity (Umeå, Sweden, June 2003), J.F. Sibeyn ed., pp. 57–72, Proceedings in Informatics 17, Carleton Scientific, 2003. This work has been partially supported by the IST Program of the European Union under contract numbers IST-1999-14186 (ALCOM-FT) and IST-2001-33116 (FLAGS), by funds from the Joint Program of Scientific and Technological Collaboration between Greece and Cyprus, by the Greek General Secretariat for Research and Technology, and by research funds from Rensselaer Polytechnic Institute and University of Cyprus. ∗Corresponding author.
PY - 2005/3/3
Y1 - 2005/3/3
N2 - 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.
AB - 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.
KW - Distributed computing
KW - Linearizability
KW - Lower bounds
KW - Monotone Linearizability Lemma
KW - Switching networks
KW - Synchronization
UR - http://www.scopus.com/inward/record.url?scp=13844256855&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=13844256855&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2004.04.018
DO - 10.1016/j.tcs.2004.04.018
M3 - Conference article
AN - SCOPUS:13844256855
SN - 0304-3975
VL - 333
SP - 373
EP - 400
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 3
T2 - Structural Information and Communication Complexity
Y2 - 18 June 2003 through 20 June 2003
ER -