# Tight bounds for asynchronous renaming

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.

## Abstract

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.

## BibTeX

Download@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 = jacm,
volume=61,
number=3,
pages=18
}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page