ALCOMFT-TR-03-134

Costas Busch, Marios Mavronicolas and Paul Spirakis
The Cost of Concurrent, Low-contention Read-Modify-Write
Patras and Cyprus. Work packages 2 and 4. December 2003.

Abstract: We embark on a study of 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. We consider a natural class of monotone RMW operations associated with monotone groups, a certain class of algebraic groups introduced here. The popular Fetch&Add and Fetch&Multiply operations are examples from the class.

Our chief combinatorial instrument is a Monotone Linearizability Lemma, which establishes inherent ordering constraints of linearizability for a certain class of executions of any distributed system that implements a monotone RMW operation.

The end results of our study specifically apply to implementations of (monotone) RMW operations that are based on switching networks, a recent class of concurrent, low-contention data structures that generalize counting networks [AHS94] (which implemented the traditional Fetch&Increment operation). These results are negative; they are shown through the Monotone Linearizability Lemma. In particular, we derive the first lower bounds on size (the number of switches in the network) and latency (the maximum number of switches traversed) for any (non-trivial) switching network implementing a monotone RMW operation:

• If the network incurs low contention, then its size must be infinite. For switches with a finite number of states, bounded concurrency (number of concurrent processes) already suffices to prove the lower bound, while a separate proof employs unbounded concurrency in order to compensate for switches with an infinite number of states.

  Since Fetch&Increment is implementable with counting networks of finite size [AHS94], these lower bounds imply a space complexity separation between Fetch&Increment and any monotone RMW operation in the model of switching networks.

• Any such network has sequential executions with n processes and latency Omega (n).

  Since Fetch&Increment is implementable with counting networks of latency Theta (lg n) [BM98,KP92], this lower bound implies a time complexity separation between Fetch&Increment and any monotone RMW operation in the model of switching networks.

Together our lower bounds provide a mathematical explanation for the observed inability of researchers over the last twelve years to extend counting networks, while keeping them finite-sized, high-concurrency, low-latency and low-contention, in order to perform tasks more complex than just incrementing a counter by one, but yet as simple as adding an arbitrary value to a counter.

Postscript file: ALCOMFT-TR-03-134.ps.gz (150 kb).