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

https://hal.inria.fr/hal-00856744
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

File

podc13_renaming.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00856744, version 1

Citation

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⟩

Share

Metrics

Record views

642

Files downloads

275