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.
lower bounds time complexity mutual exclusion atomicity local spinning shared memory