Mutual Exclusion with O(log^2 Log n) Amortized Work
Mutual Exclusion with O(log^2 Log n) Amortized Work
复制标题
具有 O(log^2 Log n) 摊销工作量的互斥
DOI：
10.1109/focs.2011.84
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Seth Gilbert
中科院分区：
文献类型：
--
作者：
M. A. Bender;Seth Gilbert
本文提出了一种新的互斥算法，在该算法中，每条通过临界截面的通道都以高概率平摊O（log^2 log n）个rmr。该算法在一个标准的异步、本地旋转、共享内存模型中与一个无关的对手操作。它保证了每个过程都有高概率进入临界区域。该算法利用互斥和近似计数之间的联系来实现其高效的性能。
This paper presents a new algorithm for mutual exclusion in which each passage through the critical section costs amortized O(log^2 log n) RMRs with high probability. The algorithm operates in a standard asynchronous, local spinning, shared memory model with an oblivious adversary. It guarantees that every process enters the critical section with high probability. The algorithm achieves its efficient performance by exploiting a connection between mutual exclusion and approximate counting.