Thumbnail
Access Restriction
Open

Author Alistarh, Dan ♦ Aspnes, James ♦ Censor-Hillel, Keren ♦ Gilbert, Seth ♦ Guerraoui, Rachid
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Tight Bound ♦ Distributed Computing ♦ Fundamental Problem ♦ Exponential Separation ♦ Deterministic Concurrent Fetch-andincrement Counter ♦ Shared-memory Renaming ♦ Current Execution ♦ Monotone-consistent Counter ♦ Mutual Exclusion ♦ Small Namespace ♦ Distinct Identifier ♦ Algorithmic Side ♦ Individual Bound ♦ Total Step Complexity ♦ Randomized Approximate Counter Implementation ♦ Randomized Solution ♦ First Tight Bound ♦ Sublinear Time ♦ New Reduction ♦ Logarithmic Step Complexity ♦ Process Step ♦ Strong Adaptive Renaming Algorithm ♦ Sorting Network ♦ Linearizable Fetchand-increment Register ♦ Polylogarithmic Cost ♦ Strong Adversary ♦ Logarithmic Factor ♦ Size Ck ♦ Step Complexity ♦ New Tight Bound
Abstract This paper presents the first tight bounds on the 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 sub-exponential 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-andincrement 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 Ω(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 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 fetchand-increment registers with polylogarithmic cost.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2011-01-01