Time/Contention Trade-Offs for Multiprocessor Synchronization

AbstractWe establish trade-offs between time complexity and write- and access-contention for solutions to the mutual exclusion problem. Thewrite-contention(access-contention) of a concurrent program is the number of processes that may be simultaneously enabled to write (access by reading and/or writing) the same shared variable. Our notion of time complexity distinguishes between local and remote accesses of shared memory. We show that, for anyN-process mutual exclusion algorithm, if write-contention isw, and if at mostvremote variables can be accessed by a single atomic operation, then there exists an execution involving only one process in which that process executesΩ(logvwN) remote operations for entry into its critical section. We further show that, among these operations,[formula]distinct remote variables are accessed. For algorithms with access-contentionc, we show that the latter bound can be improved toΩ(logvcN). The last two of these bounds imply that a trade-off between contention and time complexity exists even if coherent caching techniques are employed. In most shared-memory multiprocessors, an atomic operation may access only a constant number of remote variables. In fact, most commonly-available synchronization primitives (e.g., read, write, test-and-set, load-and-store, compare-and-swap, and fetch-and-add) access only one remote variable. In this case, the first and the last of our bounds are asymptotically tight. Our results have a number of important implications regarding specific concurrent programming problems. For example, the time bounds that we establish apply not only to the mutual exclusion problem, but also to a class of decision problems that includes the leader-election problem. Also, because the execution that establishes these bounds involves only one process, it follows that “fast mutual exclusion” requires arbitrarily high write-contention. Although such conclusions are interesting in their own right, we believe that the most important contribution of our work is to identify a time complexity measure for asynchronous concurrent programs that strikes a balance between being conceptually simple and having a tangible connection to real performance