Please use this identifier to cite or link to this item:
Title: Optimal-time adaptive strong renaming, with applications to counting
Authors: Alistarh, D.
Aspnes, J.
Censor-Hillel, K.
Gilbert, S. 
Zadimoghaddam, M.
Keywords: adaptive algorithms
distributed computing
lower bounds
shared memory
sorting networks
Issue Date: 2011
Citation: Alistarh, D.,Aspnes, J.,Censor-Hillel, K.,Gilbert, S.,Zadimoghaddam, M. (2011). Optimal-time adaptive strong renaming, with applications to counting. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing : 239-248. ScholarBank@NUS Repository.
Abstract: We give two new randomized algorithms for strong renaming, both of which work against an adaptive adversary in asynchronous shared memory. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of n processes with step complexity O(log3 n). The second transforms any sorting network into a strong adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a strong adaptive renaming algorithm with step complexity O(log k), where k is the contention in the current execution. We show this to be optimal based on a classic lower bound of Jayanti. We also show that any such strong renaming protocol can be used to build a monotone-consistent counter with logarithmic step complexity (at the cost of adding a max register) or a linearizable fetch-and-increment register (at the cost of increasing the step complexity by a logarithmic factor). © 2011 ACM.
Source Title: Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
ISBN: 9781450307192
DOI: 10.1145/1993806.1993850
Appears in Collections:Staff Publications

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


checked on Nov 15, 2018

Page view(s)

checked on Nov 3, 2018

Google ScholarTM



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