Early Deciding Synchronous Renaming in O(log f ) 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 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].
Document type :
Reports
[Research Report] 2012
Liste complète des métadonnées

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-00687555
Contributor : Corentin Travers <>
Submitted on : Monday, May 14, 2012 - 4:02:59 PM
Last modification on : Monday, October 2, 2017 - 4:06:02 PM
Document(s) archivé(s) le : Thursday, December 15, 2016 - 12:02:37 AM

File

htmod-full.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00687555, version 2

Collections

Citation

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

Share

Metrics

Record views

150

Document downloads

53