Time Bounds for Mutual Exclusion and Related Problems

We establish trade-o s between time complexity and write- and access-contention for solutions to the mutual exclusion problem. The write-contention (accesscontention) of a concurrent program is the number of processes that may be simultaneously enabled to write (access) the same shared variable. Our notion of time complexity distinguishes between local and remote references to shared memory. We show that, for any N-process mutual exclusion algorithm with write-contention w, there exists an execution involving only one process in which that process executes (log w N) remote memory references for entry into its critical section. We further show that among these remote references, ( p log w N) distinct remote variables are accessed. For algorithms with access-contention c, we show that the latter bound can be improved to (log c N). The last two of these results imply that a trade-o between contention and time complexity exists even if coherent caching techniques are employed. Because the execution that establishes these bounds involves only one process, our results show that \fast mutual exclusion " requires arbitrarily high writecontention. We show that these bounds hold when using any ofavariety of synchronization primitives, including read, write, test-and-set, load-and-store, compare-andswap, and fetch-and-add, and that they can be generalized to apply when using even stronger primitives. Our results can be extended to apply to a class of decision problems that includes the leader-election problem. The time bounds that we establish are the rst of their kin