Randomized loose renaming in O(log log n) time

International audienceRenaming 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