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/78251
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 Feb 22, 2018

WEB OF SCIENCETM
Citations

2
checked on Jan 29, 2018

Page view(s)

20
checked on Feb 19, 2018

Google ScholarTM

Check

Altmetric


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