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

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