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

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 \emphconstant 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( logf ) communication rounds. In the wait-free case, i.e. for f = n − 1, our upper bounds match the Ω( logn ) lower bound of Chaudhuri et al. [13].


Editor(s):
Even, Guy
Halldórsson, Magnús M.
Published in:
Structural Information and Communication Complexity, 7355, 195-206
Presented at:
19th International Colloquium, SIROCCO, Reykjavik, Iceland, June 30-July 2, 2012
Year:
2012
Publisher:
Berlin, Heidelberg, Springer Berlin Heidelberg
Laboratories:




 Record created 2015-05-29, last modified 2018-03-17

Preprint:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)