Skip to Main content Skip to Navigation
Conference papers

Randomized loose renaming in O(log log n) time

Abstract : Renaming is a classic distributed coordination task in which a set of processes must pick distinct identifiers from a small namespace. In this paper, we consider the time complexity of this problem when the namespace is linear in the number of participants, a variant known as loose renaming. We give a non-adaptive algorithm with $O( \log \log n )$ (individual) step complexity, where $n$ is a known upper bound on contention, and an adaptive algorithm with step complexity $O( (\log \log k)^2 )$, where $k$ is the actual contention in the execution. We also present a variant of the adaptive algorithm which requires $O( k \log \log k )$ \emph{total} process steps. All upper bounds hold with high probability against a strong adaptive adversary. We complement the algorithms with an $\Omega( \log \log n )$ expected time lower bound on the complexity of randomized renaming using test-and-set operations and linear space. The result is based on a new coupling technique, and is the first to apply to non-adaptive randomized renaming. Since our algorithms use $O(n)$ test-and-set objects, our results provide matching bounds on the cost of loose renaming in this setting.
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download
Contributor : George Giakkoupis <>
Submitted on : Monday, September 2, 2013 - 1:55:51 PM
Last modification on : Tuesday, June 15, 2021 - 4:15:01 PM
Long-term archiving on: : Tuesday, December 3, 2013 - 5:16:09 AM


Files produced by the author(s)


  • HAL Id : hal-00856744, version 1


Dan Alistarh, James Aspnes, George Giakkoupis, Philipp Woelfel. Randomized loose renaming in O(log log n) time. 32nd ACM Symposium on Principles of Distributed Computing (PODC), Jul 2013, Montreal, Canada. ⟨hal-00856744⟩



Record views


Files downloads