Please use this identifier to cite or link to this item:
Title: Tight bounds for asynchronous renaming
Authors: Alistarh, D.
Aspnes, J.
Censor-Hillel, K.
Gilbert, S. 
Guerraoui, R.
Keywords: Concurrent data structures
Distributed computing
Lower bounds
Shared memory
Issue Date: 2014
Citation: Alistarh, D., Aspnes, J., Censor-Hillel, K., Gilbert, S., Guerraoui, R. (2014). Tight bounds for asynchronous renaming. Journal of the ACM 61 (3) : -. ScholarBank@NUS Repository.
Abstract: 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 ω(k) 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 ω(klog(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. © 2014 ACM.
Source Title: Journal of the ACM
ISSN: 1557735X
DOI: 10.1145/2597630
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Jan 12, 2019


checked on Jan 2, 2019

Page view(s)

checked on Dec 21, 2018

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.