Please use this identifier to cite or link to this item:
|Title:||Optimal-time adaptive strong renaming, with applications to counting|
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Dec 13, 2017
checked on Dec 9, 2017
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.