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
Citation: 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 Aug 11, 2018

WEB OF SCIENCETM
Citations

2
checked on Jul 17, 2018

Page view(s)

52
checked on May 26, 2018

Google ScholarTM

Check

Altmetric


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