Namespace | EPFL Graph Search

In computing, a namespace is a set of signs (names) that are used to identify and refer to objects of various kinds. A namespace ensures that all of a given set of objects have unique names so that they can be easily identified. Namespaces are commonly structured as hierarchies to allow reuse of names in different contexts. As an analogy, consider a system of naming of people where each person has a given name, as well as a family name shared with their relatives. If the first names of family members are unique only within each family, then each person can be uniquely identified by the combination of first name and family name; there is only one Jane Doe, though there may be many Janes. Within the namespace of the Doe family, just "Jane" suffices to unambiguously designate this person, while within the "global" namespace of all people, the full name must be used. Prominent examples for namespaces include s, which assign names to files. Some programming languages organize their vari

Fast Randomized Test-and-Set and Renaming

Hagit Albo Attiya, Dan Alistarh, Seth Gilbert, Andrei Giurgiu, Rachid Guerraoui

Most people believe that renaming is easy: simply choose a name \emph{at random}; if more than one process selects the same name, then try again. We highlight the issues that occur when trying to implement such a scheme and shed new light on the read-write complexity of randomized renaming in an asynchronous environment. At the heart of our new perspective stands an adaptive implementation of a randomized test-and-set object, that has poly-logarithmic step complexity per operation, with high probability. Interestingly, our implementation is anonymous, as it does not require process identifiers. Based on this implementation, we present two new randomized renaming algorithms. The first ensures a tight namespace of

n

names using

O( n \log^4 n)

total steps, with high probability. This improves on the best previously known namespace-optimal algorithm by almost a quadratic factor. The second algorithm achieves a namespace of size

k (1 + \epsilon)

using

O( k \log^4 k / \log^2 (1 + \epsilon) )

total steps, both with high probability, where

k

is the total contention in the execution. It is the first \emph{adaptive} randomized renaming algorithm, and it improves on existing deterministic solutions by providing a smaller namespace, and by lowering complexity.

2010

Fast Randomized Test-and-Set and Renaming

Hagit Albo Attiya, Dan Alistarh, Seth Gilbert, Andrei Giurgiu, Rachid Guerraoui

n

names using

O( n \log^4 n)

total steps, with high probability. This significantly improves on the complexity of the best previously known namespace-optimal algorithms. The second algorithm achieves a namespace of size

k (1 + \epsilon)

using

O( k \log^4 k / \log^2 (1 + \epsilon) )

total steps, both with high probability, where

k

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010

Tight Bounds for Asynchronous Renaming

Dan Alistarh, Seth Gilbert, Rachid Guerraoui

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 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.

Association for Computing Machinery2014

Fast Randomized Test-and-Set and Renaming

Hagit Albo Attiya, Dan Alistarh, Seth Gilbert, Andrei Giurgiu, Rachid Guerraoui

n

names using

O( n \log^4 n)

total steps, with high probability. This improves on the best previously known namespace-optimal algorithm by almost a quadratic factor. The second algorithm achieves a namespace of size

k (1 + \epsilon)

using

O( k \log^4 k / \log^2 (1 + \epsilon) )

total steps, both with high probability, where

k

2010

Fast Randomized Test-and-Set and Renaming

Hagit Albo Attiya, Dan Alistarh, Seth Gilbert, Andrei Giurgiu, Rachid Guerraoui

n

names using

O( n \log^4 n)

total steps, with high probability. This significantly improves on the complexity of the best previously known namespace-optimal algorithms. The second algorithm achieves a namespace of size

k (1 + \epsilon)

using

O( k \log^4 k / \log^2 (1 + \epsilon) )

total steps, both with high probability, where

k

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2010