Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download
Contributor : Corentin Travers Connect in order to contact the contributor
Submitted on : Monday, May 19, 2014 - 11:51:22 AM
Last modification on : Saturday, June 25, 2022 - 10:34:49 AM
Long-term archiving on: : Monday, April 10, 2017 - 11:42:58 PM


Files produced by the author(s)


  • HAL Id : hal-00992782, version 1



Dan Alistarh, Hagit Attiya, Rachid Guerraoui, Corentin Travers. Early Deciding Synchronous Renaming in O( logf ) Rounds or Less. SIROCCO, 2012, Unknown, pp.195-206. ⟨hal-00992782⟩



Record views


Files downloads