000201457 001__ 201457
000201457 005__ 20190317000002.0
000201457 0247_ $$2doi$$a10.1145/2597630
000201457 02470 $$2ISI$$a000337201400004
000201457 037__ $$aARTICLE
000201457 245__ $$aTight Bounds for Asynchronous Renaming
000201457 269__ $$a2014
000201457 260__ $$bAssociation for Computing Machinery$$c2014$$aNew York
000201457 300__ $$a51
000201457 336__ $$aJournal Articles
000201457 520__ $$aThis 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.
000201457 6531_ $$aTheory
000201457 6531_ $$aAlgorithms
000201457 6531_ $$aPerformance
000201457 6531_ $$aDistributed computing
000201457 6531_ $$ashared memory
000201457 6531_ $$aconcurrent data structures
000201457 6531_ $$arenaming
000201457 6531_ $$alower bounds
000201457 700__ $$0242985$$g177872$$uMicrosoft Res Cambridge, Cambridge CB1 2FB, England$$aAlistarh, Dan
000201457 700__ $$uYale Univ, Dept Comp Sci, New Haven, CT 06520 USA$$aAspnes, James
000201457 700__ $$uTechnion Israel Inst Technol, IL-3200003 Haifa, Israel$$aCensor-Hillel, Keren
000201457 700__ $$0240435$$g176464$$uNatl Univ Singapore, Dept Comp Sci, Singapore 119077, Singapore$$aGilbert, Seth
000201457 700__ $$aGuerraoui, Rachid$$g105326$$0240335
000201457 773__ $$j61$$tJournal of The ACM$$k3
000201457 8564_ $$uhttps://infoscience.epfl.ch/record/201457/files/tight_bounds_a18-alistarh.pdf$$zPublisher's version$$s2013055$$yPublisher's version
000201457 909C0 $$xU10407$$0252114$$pDCL
000201457 909CO $$ooai:infoscience.tind.io:201457$$qGLOBAL_SET$$pIC$$particle
000201457 917Z8 $$x166927
000201457 917Z8 $$x166927
000201457 917Z8 $$x166927
000201457 917Z8 $$x166927
000201457 937__ $$aEPFL-ARTICLE-201457
000201457 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000201457 980__ $$aARTICLE