Please use this identifier to cite or link to this item: https://doi.org/10.1145/1993806.1993850
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
renaming
shared memory
sorting networks
Issue Date: 2011
Source: 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. https://doi.org/10.1145/1993806.1993850
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
URI: http://scholarbank.nus.edu.sg/handle/10635/40517
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.

SCOPUSTM   
Citations

14
checked on Dec 13, 2017

Page view(s)

65
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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