Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/78251
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.
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
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 May 11, 2018

WEB OF SCIENCETM
Citations

2
checked on May 15, 2018

Page view(s)

23
checked on Jul 6, 2018

Google ScholarTM

Check


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