Access Restriction

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

   Open content in new tab
Source: ACM Digital Library