Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Rachid Guerraoui. Tight bounds for asynchronous renaming. Journal of the Association for Computing Machinery, 61(3):18, May 2014.
This paper presents the first tight bounds on the 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 Ω(k) process steps for deterministic renaming into any namespace of size sub-exponential 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 Ω(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 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.
@article{AlistarhACHGG2014,
author = {Dan Alistarh and James Aspnes and Keren Censor-Hillel and Seth Gilbert and Rachid Guerraoui},
title = {Tight bounds for asynchronous renaming},
month=may,
year = 2014,
journal={Journal of th6e ACM},
volume=61,
number=3,
pages=18
}