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].