# Optimal-time adaptive tight renaming, with applications to counting

Dan Alistarh, James Aspnes, Keren Censor-Hillel, Seth Gilbert, and Morteza Zadimoghaddam.
Optimal-time adaptive tight renaming, with applications to counting.
*Thirtieth Annual ACM SIGACT-SIGOPS Symposium on Principles of
Distributed Computing*, June 2011, pp. 239–248.

## Abstract

We give two new randomized algorithms for strong renaming, both of which work against an adaptive adversary in asynchronous shared memory. The first uses repeated sampling over a sequence of arrays of decreasing size to assign unique names to each of n processes with step complexity O(log³ n). The second transforms any sorting network into a strong adaptive renaming protocol, with an expected cost equal to the depth of the sorting network. Using an AKS sorting network, this gives a strong adaptive renaming algorithm with step complexity O(log k), where k is the contention in the current execution. We show this to be optimal based on a classic lower bound of Jayanti. We also show that any such strong renaming protocol can be used to build a monotone-consistent counter with logarithmic step complexity (at the cost of adding a max register) or a linearizable fetch-and-increment register (at the cost of increasing the step complexity by a logarithmic factor).

- PODC 2011 proceedings version:
**PDF**.

## BibTeX

Download@inproceedings{AlistarhACHGZ2011,
author = {Dan Alistarh and James Aspnes and Keren Censor-Hillel and Seth Gilbert and Morteza Zadimoghaddam},
title = {Optimal-time adaptive tight renaming, with applications to counting},
month = jun,
year = 2011,
booktitle = {Proceedings of the Thirtieth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing},
pages={239--248},
}

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page