An improved lower bound for the time complexity of mutual exclusion
An improved lower bound for the time complexity of mutual exclusion
复制标题
改进的互斥时间复杂度下界
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Yong
中科院分区：
文献类型：
--
作者：
James H. Anderson;Yong
抽象的。我们建立了一个下界的$\Omega（\log N/\log\log N）$远程内存引用的N进程互斥算法的基础上读，写，或比较原语，如测试和设置和比较和交换。我们的界改进了早期的下界$\Omega（\log\log N/\log\log N）$由Cypher建立。我们的下界很重要，原因有二。首先，它几乎与基于读、写或比较原语的最知名算法的$\Theta（\log N）$时间复杂度相匹配。其次，我们的下限表明，从渐近的角度来看，比较原语在实现局部自旋互斥算法时并不比读和写更好。因此，如果对可伸缩同步感兴趣，比较原语可能不是在硬件中提供的最佳选择。
Abstract. 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.