Randomized loose renaming in O(log log n) time

Dan Alistarh, James Aspnes, George Giakkoupis, and Philipp Woelfel. Randomized loose renaming in O(log log n) time. 2013 ACM Symposium on Principles of Distributed Computing, July 2013, pp. 200–209.

Abstract

Renaming is a classic distributed coordination task in which a set of processes must pick distinct identifiers from a small namespace. In this paper, we consider the time complexity of this problem when the namespace is linear in the number of participants, a variant known as loose renaming. We give a non-adaptive algorithm with O(log log n) (individual) step complexity, where n is a known upper bound on contention, and an adaptive algorithm with step complexity O((log log k)²), where k is the actual contention in the execution. Both bounds hold with high probability against a strong adaptive adversary. The running time improvement over previously known solutions is exponential.

We complement the algorithms with an Ω(log log n) expected time lower bound on the complexity of randomized renaming using test-and-set operations and linear space. The result is based on a new coupling technique, and is the first to apply to non-adaptive randomized renaming. Since our algorithms use O(n) test-and-set objects, our results provide matching bounds on the cost of loose renaming in this setting.

BibTeX

Download
@inproceedings{AlistarhAGW2013,
author = {Dan Alistarh and James Aspnes and George Giakkoupis and Philipp Woelfel},
title = {Randomized loose renaming in $O(\log \log n)$ time},
month=jul,
year = 2013,
booktitle={2013 ACM Symposium on Principles of Distributed Computing},
pages={200--209}
}

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page