201457
20190317000002.0
10.1145/2597630
doi
000337201400004
ISI
ARTICLE
Tight Bounds for Asynchronous Renaming
New York
2014
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
Alistarh, Dan
Microsoft Res Cambridge, Cambridge CB1 2FB, England
177872
242985
Aspnes, James
Yale Univ, Dept Comp Sci, New Haven, CT 06520 USA
Censor-Hillel, Keren
Technion Israel Inst Technol, IL-3200003 Haifa, Israel
Gilbert, Seth
Natl Univ Singapore, Dept Comp Sci, Singapore 119077, Singapore
176464
240435
Guerraoui, Rachid
105326
240335
3
Journal of The ACM
61
Publisher's version
2013055
Publisher's version
http://infoscience.epfl.ch/record/201457/files/tight_bounds_a18-alistarh.pdf
DCL
252114
U10407
oai:infoscience.tind.io:201457
article
IC
GLOBAL_SET
166927
166927
166927
166927
EPFL-ARTICLE-201457
EPFL
PUBLISHED
REVIEWED
ARTICLE