An improved lower bound for the time complexity of mutual exclusion
James Horton Anderson, Yong-Jik Kim · 2001
We establish a lower bound of 23 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 compareand -swap. Our bound improves an earlier lower bound of 34 log N= log log log N) established by Cypher. Our lower bound is of importance for two reasons. First, it almost matches the (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.