Prof. Daniel Hendler

Mutual exclusion is a fundamental distributed coordination problem. Shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory refaerences (RMRs) metric. To ensure the correctness of conacurrent algorithms in general, and mutual exclusion algoarithms in particular, it is often required to prohibit certain re-orderings of memory instructions that may compromise correctness, by inserting memory fence (a.k.a. memory bararier ) instructions. Memory fences incur non-negligible overahead and may significantly increase time complexity. A mutual exclusion algorithm is adaptive to total conatention (or simply adaptive), if the time complexity of every passage (an entry to the critical section and the correspondaing exit) is a function of total contention, that is, the number of processes, k, that participate in the execution in which that passage is performed. We say that an algorithm A is f-adaptive (and that f is an adaptivity function of A), if the time complexity of every passage in A is Of (k)). Adapative implementations are desirable when contention is much smaller than the total number of processes, n, sharing the implementation. Recent work [5] presented the first read/write mutual exaclusion algorithm with asymptotically optimal complexity under both the RMRs and fences metrics: each passage through the critical section incurs O(log n) RMRs and a constant number of fences. The algorithm works in the popaular Total Store Ordering (TSO) model. The algorithm of [5] is non-adaptive, however, and they posed the question of whether there exists an adaptive mutual exclusion algorithm with the same complexities. We provide a negative answer to this question, thus capaturing an inherent cost of adaptivity. In fact, we prove a stronger result: Adaptive read/write mutual exclusion algorithms with constant fence complexity do not exist, regardaless of their RMR complexity. This result follows from a genaeral tradeoff that we establish for such algorithms, between the fence complexity and the growth rate of adaptivity funcations. Specifically, we prove that the fence complexity of any such algorithm with a linear (or sub-linear) adaptivity funcation is Q(loglog n). The tradeoff holds for implementations that may use compare-and-swap operations, in addition to reads and writes. We show that our results apply also to obstruction-free implementations of well-known objects, such as counters, stacks and queues.