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

Abstract. Renaming is a fundamental problem in distributed comput-ing, in which a set of n processes need to pick unique names from a names-pace 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 lim-ited to O( n), while for general f ≤ n−1 renaming can always be solved inO(log f) communication rounds. In the wait-free case, i.e. for f = n−1, our upper boundsmatch theΩ(logn) lower bound of Chaudhuri et al. [13].