An improved lower bound for the time complexity of mutual exclusion

We establish a lower bound of $\Omega(\log N/\log\log N)$ remote memory references for N-process mutual exclusion algorithms based on reads, writes, or comparison primitives such as test-and-set and compare-and-swap. Our bound improves an earlier lower bound of $\Omega(\log\log N/\log\log\log N)$ established by Cypher. Our lower bound is of importance for two reasons. First, it almost matches the $\Theta(\log N)$ time complexity of the best known algorithms based on reads, writes, or comparison primitives. Second, our lower bound suggests that it is likely that, from an asymptotic standpoint, comparison primitives are no better than reads and writes when implementing local-spin mutual exclusion algorithms. Thus, comparison primitives may not be the best choice to provide in hardware if one is interested in scalable synchronization.