Please use this identifier to cite or link to this item: https://doi.org/10.1109/FOCS.2011.84
Title: Mutual exclusion with O(log 2 log n) amortized work
Authors: Bender, M.A.
Gilbert, S. 
Issue Date: 2011
Source: Bender, M.A., Gilbert, S. (2011). Mutual exclusion with O(log 2 log n) amortized work. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS : 728-737. ScholarBank@NUS Repository. https://doi.org/10.1109/FOCS.2011.84
Abstract: 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. © 2011 IEEE.
Source Title: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
URI: http://scholarbank.nus.edu.sg/handle/10635/40528
ISBN: 9780769545714
ISSN: 02725428
DOI: 10.1109/FOCS.2011.84
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

19
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

1
checked on Nov 18, 2017

Page view(s)

46
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.