Randomized mutual exclusion with sub-logarithmic RMR-complexity
Randomized mutual exclusion with sub-logarithmic RMR-complexity
复制标题
具有亚对数 RMR 复杂度的随机互斥
DOI：
10.1007/s00446-011-0128-6
复制
发表时间：
2011
影响因子：
1.3
通讯作者：
Philipp Woelfel
中科院分区：
文献类型：
--
作者：
Danny Hendler;Philipp Woelfel
互斥是一个基本的分布式协调问题。共享内存互斥的研究集中在本地自旋算法，并使用远程内存引用（RMR）度量。Attiya、Hendler和Woelfel（第40届STOC，2008年）建立了一个Ω（log N）下限，用于描述进程进入和退出临界区时所发生的RMR数量，其中N是系统中的进程数量。这与Yang和安德森（Distrib. Comput. 9（1）：51-60，1995）。上限和下限适用于仅使用读和写操作的算法。Attiya等人的下界，然而，仅适用于确定性算法。是否随机互斥算法，只使用读和写，可以实现亚对数预期的RMR复杂性的问题仍然悬而未决。我们回答这个问题是肯定的，提出饥饿免费的随机互斥算法的该高速缓存一致（CC）和分布式共享内存（DSM）模型，有子对数预期RMR复杂性对强大的对手。更具体地说，每个过程每次通过入口和出口段都会产生O（log N / log log N）的RMR，而在最坏的情况下，RMR的数量是O（log N）。
Mutual exclusion is a fundamental distributed coordination problem. Shared-memory mutual exclusion research focuses on local-spin algorithms and uses the remote memory references (RMRs) metric. Attiya, Hendler, and Woelfel (40th STOC, 2008) established an Ω(log N) lower bound on the number of RMRs incurred by processes as they enter and exit the critical section, where N is the number of processes in the system. This matches the upper bound of Yang and Anderson (Distrib. Comput. 9(1):51–60, 1995). The upper and lower bounds apply for algorithms that only use read and write operations. The lower bound of Attiya et al., however, only holds for deterministic algorithms. The question of whether randomized mutual exclusion algorithms, using reads and writes only, can achieve sub-logarithmic expected RMR complexity remained open. We answer this question in the affirmative by presenting starvation-free randomized mutual exclusion algorithms for the cache coherent (CC) and the distributed shared memory (DSM) model that have sub-logarithmic expected RMR complexity against the strong adversary. More specifically, each process incurs an expected number of O(log N / log log N) RMRs per passage through the entry and exit sections, while in the worst case the number of RMRs is O(log N).