Optimal-time adaptive strong renaming, with applications to counting

Alistarh D-A, Aspnes J, Censor Hillel K, Gilbert S, Zadimoghaddam M. 2011. Optimal-time adaptive strong renaming, with applications to counting. PODC: Principles of Distributed Computing, 239–248.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
Alistarh, Dan-AdrianIST Austria; Aspnes, James; Censor Hillel, Keren; Gilbert, Seth; Zadimoghaddam, Morteza
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).
Publishing Year
Date Published
2011-01-01
Acknowledgement
We would like to thank Hagit Attiya, Rachid Guerraoui and Prasad Jayanti for useful discussions and support. We would also like to thank the anonymous reviewers for many useful comments.
Page
239 - 248
Conference
PODC: Principles of Distributed Computing
IST-REx-ID
761

Cite this

Alistarh D-A, Aspnes J, Censor Hillel K, Gilbert S, Zadimoghaddam M. Optimal-time adaptive strong renaming, with applications to counting. In: ACM; 2011:239-248. doi:10.1145/1993806.1993850
Alistarh, D.-A., Aspnes, J., Censor Hillel, K., Gilbert, S., & Zadimoghaddam, M. (2011). Optimal-time adaptive strong renaming, with applications to counting (pp. 239–248). Presented at the PODC: Principles of Distributed Computing, ACM. https://doi.org/10.1145/1993806.1993850
Alistarh, Dan-Adrian, James Aspnes, Keren Censor Hillel, Seth Gilbert, and Morteza Zadimoghaddam. “Optimal-Time Adaptive Strong Renaming, with Applications to Counting,” 239–48. ACM, 2011. https://doi.org/10.1145/1993806.1993850.
D.-A. Alistarh, J. Aspnes, K. Censor Hillel, S. Gilbert, and M. Zadimoghaddam, “Optimal-time adaptive strong renaming, with applications to counting,” presented at the PODC: Principles of Distributed Computing, 2011, pp. 239–248.
Alistarh D-A, Aspnes J, Censor Hillel K, Gilbert S, Zadimoghaddam M. 2011. Optimal-time adaptive strong renaming, with applications to counting. PODC: Principles of Distributed Computing, 239–248.
Alistarh, Dan-Adrian, et al. Optimal-Time Adaptive Strong Renaming, with Applications to Counting. ACM, 2011, pp. 239–48, doi:10.1145/1993806.1993850.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar