@article{Alistarh:201457,
title = {Tight Bounds for Asynchronous Renaming},
author = {Alistarh, Dan and Aspnes, James and Censor-Hillel, Keren and Gilbert, Seth and Guerraoui, Rachid},
publisher = {Association for Computing Machinery},
journal = {Journal of The ACM},
address = {New York},
number = {3},
volume = {61},
pages = {51},
year = {2014},
abstract = {This article presents the first tight bounds on the time complexity of shared-memory renaming, a fundamental problem in distributed computing in which a set of processes need to pick distinct identifiers from a small namespace. We first prove an individual lower bound of P(h) process steps for deterministic renaming into any namespace of size subexponential in k, where k is the number of participants. The bound is tight: it draws an exponential separation between deterministic and randomized solutions, and implies new tight bounds for deterministic concurrent fetch-and-increment counters, queues, and stacks. The proof is based on a new reduction from renaming to another fundamental problem in distributed computing: mutual exclusion. We complement this individual bound with a global lower bound of Omega(k log(k/c)) on the total step complexity of renaming into a namespace of size ck, for any c >= 1. This result applies to randomized algorithms against a strong adversary, and helps derive new global lower bounds for randomized approximate counter implementations, that are tight within logarithmic factors. On the algorithmic side, we give a protocol that transforms any sorting network into a randomized strong adaptive renaming algorithm, with expected cost equal to the depth of the sorting network. This gives a tight adaptive renaming algorithm with expected step complexity O(log k), where k is the contention in the current execution. This algorithm is the first to achieve sublinear time, and it is time-optimal as per our randomized lower bound. Finally, we use this renaming protocol to build monotone-consistent counters with logarithmic step complexity and linearizable fetch-and-increment registers with polylogarithmic cost.},
url = {http://infoscience.epfl.ch/record/201457},
doi = {10.1145/2597630},
}