TY - GEN
T1 - Mutual exclusion with O(log 2 log n) amortized work
AU - Bender, Michael A.
AU - Gilbert, Seth
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/84862612669
U2 - 10.1109/FOCS.2011.84
DO - 10.1109/FOCS.2011.84
M3 - Conference contribution
AN - SCOPUS:84862612669
SN - 9780769545714
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 728
EP - 737
BT - Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
T2 - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
Y2 - 22 October 2011 through 25 October 2011
ER -