201457
20190317000002.0
doi
10.1145/2597630
ISI
000337201400004
ARTICLE
Tight Bounds for Asynchronous Renaming
2014
New York
Association for Computing Machinery
2014
51
Journal Articles
This article presents the first tight bounds on the time 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 P(h) process steps for deterministic renaming into any namespace of size subexponential 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 Omega(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 randomized 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.
Theory
Algorithms
Performance
Distributed computing
shared memory
concurrent data structures
renaming
lower bounds
242985
Alistarh, Dan
177872
Microsoft Res Cambridge, Cambridge CB1 2FB, England
Aspnes, James
Yale Univ, Dept Comp Sci, New Haven, CT 06520 USA
Censor-Hillel, Keren
Technion Israel Inst Technol, IL-3200003 Haifa, Israel
240435
Gilbert, Seth
176464
Natl Univ Singapore, Dept Comp Sci, Singapore 119077, Singapore
240335
Guerraoui, Rachid
105326
61
3
Journal of The ACM
2013055
http://infoscience.epfl.ch/record/201457/files/tight_bounds_a18-alistarh.pdf
Publisher's version
Publisher's version
252114
DCL
U10407
oai:infoscience.tind.io:201457
IC
article
GLOBAL_SET
166927
166927
166927
166927
EPFL-ARTICLE-201457
EPFL
REVIEWED
PUBLISHED
ARTICLE