Early Deciding Synchronous Renaming in O( logf ) Rounds or Less

Abstract : Renaming is a fundamental problem in distributed computing, in which a set of n processes need to pick unique names from a namespace of limited size. In this paper, we present the first early-deciding upper bounds for synchronous renaming, in which the running time adapts to the actual number of failures f in the execution. We show that, surprisingly, renaming can be solved in constant time if the number of failures √ f is limited to O( n), while for general f ≤ n − 1 renaming can always be solved in O(log f ) communication rounds. In the wait-free case, i.e. for f = n − 1, our upper bounds match the Ω(log n) lower bound of Chaudhuri et al.
Type de document :
Communication dans un congrès
Guy Even and Magnús M. Halldórsson. SIROCCO, 2012, Unknown, Springer, 7355, pp.195-206, 2012, Lecture Notes in Computer Science
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00992782
Contributeur : Corentin Travers <>
Soumis le : lundi 19 mai 2014 - 11:51:22
Dernière modification le : dimanche 22 avril 2018 - 01:12:00
Document(s) archivé(s) le : lundi 10 avril 2017 - 23:42:58

Fichier

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

Identifiants

  • HAL Id : hal-00992782, version 1

Collections

Citation

Dan Alistarh, Hagit Attiya, Rachid Guerraoui, Corentin Travers. Early Deciding Synchronous Renaming in O( logf ) Rounds or Less. Guy Even and Magnús M. Halldórsson. SIROCCO, 2012, Unknown, Springer, 7355, pp.195-206, 2012, Lecture Notes in Computer Science. 〈hal-00992782〉

Partager

Métriques

Consultations de la notice

126

Téléchargements de fichiers

132