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.
Type de document :
Communication dans un congrès
32nd ACM Symposium on Principles of Distributed Computing (PODC), Jul 2013, Montreal, Canada. 2013
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00856744
Contributeur : George Giakkoupis <>
Soumis le : lundi 2 septembre 2013 - 13:55:51
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : mardi 3 décembre 2013 - 05:16:09

Fichier

podc13_renaming.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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. 2013. 〈hal-00856744〉

Partager

Métriques

Consultations de la notice

521

Téléchargements de fichiers

222