Early Deciding Synchronous Renaming in O(log f ) Rounds or Less - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Reports (Research Report) Year : 2012

Early Deciding Synchronous Renaming in O(log f ) Rounds or Less

Dan Alistarh
  • Function : Author
  • PersonId : 923790
Hagit Attiya
  • Function : Author
  • PersonId : 915844
Rachid Guerraoui
  • Function : Author
  • PersonId : 923791

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 synchronous renaming algorithms, that adapt their running time 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. [11].
Fichier principal
Vignette du fichier
htmod-full.pdf (347.6 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-00687555 , version 1 (13-04-2012)
hal-00687555 , version 2 (14-05-2012)

Identifiers

  • HAL Id : hal-00687555 , version 2

Cite

Dan Alistarh, Hagit Attiya, Rachid Guerraoui, Corentin Travers. Early Deciding Synchronous Renaming in O(log f ) Rounds or Less. [Research Report] 2012. ⟨hal-00687555v2⟩

Collections

CNRS LARA
176 View
172 Download

Share

Gmail Facebook X LinkedIn More