### Tight Bounds for Asynchronous RenamingTight Bounds for Asynchronous Renaming

Access Restriction
Subscribed

 Author Alistarh, Dan ♦ Aspnes, James ♦ Censor-Hillel, Keren ♦ Gilbert, Seth ♦ Guerraoui, Rachid Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2014 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Distributed computing ♦ Concurrent data structures ♦ Lower bounds ♦ Renaming ♦ Shared memory 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 $Ω(\textit{k})$ process steps for deterministic renaming into any namespace of size subexponential in $\textit{k},$ where $\textit{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 $Ω(\textit{k}$ log $(\textit{k}/\textit{c}))$ on the total step complexity of renaming into a namespace of size $\textit{ck},$ for any $\textit{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 $\textit{O}(log$ $\textit{k}),$ where $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2014-06-02 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 61 Issue Number 3 Page Count 51 Starting Page 1 Ending Page 51

#### Open content in new tab

Source: ACM Digital Library