For more up-to-date notes see http://www.cs.yale.edu/homes/aspnes/classes/465/notes.pdf.

We will be mostly following the presentation in AttiyaWelch §16.3. These results are from the paper of Attiya et al., Renaming in an asynchronous environment, JACM 1990, although in AttiyaWelch they are translated from a message-passing to a shared-memory system.

1. Renaming

In the renaming problem, we have n processes, each starts with a name from some huge namespace, and we'd like to assign them each unique names from a much smaller namespace. The main application is allowing us to run algorithms that assume that the processes are given contiguous numbers, e.g. the various collect or AtomicSnapshot algorithms in which each process is assigned a unique register and we have to read all of the registers; with renaming, instead of reading a huge pile of registers in order to find the few that are actually used, we can map the processes down to a much smaller set.

Formally we have a decision problem where each process has input x_i (its original name) and output y_i, with the requirements:

Termination

Every nonfaulty process eventually decides.

Uniqueness

If p_i ≠ p_j then y_i ≠ y_j.

Anonymity

The code executed by any process depends only on its input x_i: for any execution of processes p₁..p_n with inputs x₁..x_n, and any permutation π of [1..n], there is a corresponding execution of processes p_π(1)..p_π(n) with inputs x₁..x_n in which p_π(i) performs exactly the same operations as p_i and obtains the same output y_i.

The last condition is like non-triviality for consensus: it excludes algorithms where p_i just returns i in all executions. Typically we do not have to do much to prove anonymity other than observing that all processes are running the same code.

We will be considering renaming in a shared-memory system, where we only have atomic registers to work with.

2. Performance

Conventions on counting processes:

• N = number of possible original names.
• n = maximum number of processes.
• k = number of processes that actually execute the algorithm.

Ideally, we'd like any performance measures we get to depend on k alone if possible (giving an adaptive algorithm). Next best would be something polynomial in n and k. Anything involving N is bad.

3. Order-preserving renaming

One variant of renaming considered in the Attiya et al. paper is order-preserving renaming: here we require that y_i < y_j whenever x_i < x_j. Unfortunately, this requires a very large output namespace: with t failures, any asynchronous algorithm for order-preserving renaming requires 2^t(n-t+1)-1 possible output names. This lower bound applies regardless of the model, as long as some processes may start after other processes have already been assigned names.

For the wait-free case, we have t = n-1, and the bound becomes just 2ⁿ-1. This is a simpler case than the general t-failure case but the essential idea is the same: if I've only seen a few of the processes, I need to leave room for the others.

Claim

There is no order-preserving renaming algorithm for n processes using fewer than 2ⁿ-1 names.

Proof

By induction on n. For n=1, we use 2¹-1=1 names; this is the base case. For larger n, suppose we use m names, and consider an execution in which one process p_n runs to completion first. This consumes one name y_n and leaves k names less than y_n and m-k-1 names greater than y_n. By setting all the inputs x_i for i < n either less than x_n or greater than x_n, we can force the remaining processes to choose from the remaining k or m-k-1 names. Applying the induction hypothesis, this gives k >= 2^n-1-1 and m-k-1 >= 2^n-1-1, so m = k+(m-k-1)+1 >= 2(2^n-1-1)+1 = 2ⁿ-1.

4. Wait-free renaming with 2n-1 names

Here we use Algorithm 55 from AttiyaWelch. One odd feature of the algorithm is that, as written, it is not anonymous: processes communicate using an AtomicSnapshot object and use their process ids to select which component of the snapshot array to write to. But if we think of the process ids used in the algorithm as the inputs x_i rather than the actual process ids i, then everything works. The version below makes this substitution explicit, by treating the original name i as the input.

algorithm choose-name(i)

• s ← 1
• for ever:
  • a[i] ← s
  • view ← snapshot(a)
  • if view[j] = s for some j, then:
    • r ← | { j with view[j] ≠ ⊥ and j ≤ i } |
    • s ← r-th positive integer not in { view[j] | j ≠ i and view[j] = ⊥ }
  • else:
    • return s

The array a holds proposed names for each process (indexed by the original names), or ⊥ for processes that have not proposed a name yet. If a process proposes a name and finds that no other process has proposed the same name, it takes it; otherwise it chooses a new name by first computing its rank r among the active processes and then choosing the r-th unused name. Because the rank is at most n and there are at most n-1 names used by the other processes, this always gives proposed names in the range [1..2n-1]. But it remains to show that the algorithm does in fact satisfy uniqueness and termination.

For uniqueness, consider two process with original names i and j. Suppose that i and j both decide on s. Then i sees a view in which a[i] = s and a[j] ≠ s, after which it no longer updates a[i]. Similarly, j sees a view in which a[j] = s and a[i] ≠ s, after which it no longer updates a[j]. If i's view is obtained first, then j can't see a[i] ≠ s, but the same holds if j's view is obtained first. So in either case we get a contradiction, proving uniqueness.

Termination is a bit trickier. Here we argue that no process can run forever without picking a name, by showing that if we have a set of processes that are doing this, the one with smallest original name eventually picks a name. More formally, call a process trying if it runs for infinitely many steps without choosing a name. Then in any execution with at least one trying process, eventually we reach a configuration where all processes have either finished or are trying. In some subsequent configuration, all the processes have written to the a array at least once; after this point, any process reading the a array will see the same set of original names and compute the same rank r for itself.

Now look at the trying process i with the smallest original name, and suppose it has rank r. Let F = { z₁ < z₂ ... } be the set of "free names" that are not proposed in a by any of the finished processes. Observe that no trying process j != i ever proposes a name in { z₁ ... z_r }, because any such process has rank greater than r. This leaves z_r open for i to claim, provided the other names in { z₁ ... z_r } eventually become free. But this will happen, because only trying processes may have proposed these names (early on in the execution, when the finished processes hadn't finished yet), and the trying processes eventually propose new names that are not in this range. So eventually process i proposes z_r, sees no conflict, and finishes, contradicting the assumption that it is trying.

Note that we haven't proved any complexity bounds on this algorithm at all, but we know that the snapshot alone takes at least Omega(N) time and space.

5. Lower bounds

Most work on lower bounds has concentrated on bounding the size of the name space. This is tricky, and the current known lower bounds depend on a reduction to problems in topology. See TopologicalMethodsInDistributedComputing for a description of the overall approach and some simple cases. For more details, a good place to start might be Castañeda and Rajsbaum, New combinatorial topology upper and lower bounds for renaming, PODC 2008.

6. Long-lived renaming

In long-lived renaming a process can release a name for later use by other processes (or the same process, if it happens to run choose-name again). Now the bound on the number of names needed is 2k-1, where k is the maximum number of concurrently active processes. The algorithm above can be converted to a long-lived renaming algorithm by adding the following release-name procedure:

procedure release-name(i)

• a[i] ← ⊥

Here the termination requirement is weakened slightly, to say that some process always makes progress in choose-name (see ObstructionFreedom). It may be, however, that there is some process that never successfully obtains a name, because it keeps getting stepped on by other processes zipping in and out of choose-name and release-name.

7. Renaming without snapshots

Moir and Anderson, Wait-free algorithms for fast, long-lived renaming, Science of Computer Programming 25:1–39, 1995, gives a renaming protocol that is somewhat easier to understand and doesn't require taking snapshots over huge arrays. A downside is that the basic version requires k(k+1)/2 names to handle k active processes (we'll be lazy and only prove k²).

7.1. Splitters

The Moir-Anderson renaming protocol uses a network of splitters.¹ Each splitter is a are widget, built from a pair of atomic registers, that assigns to each processes that arrives at it the value right, down, or stop. The useful property of splitters is that if at least one process arrives at a splitter, then (a) at least one process either goes right or gets stop; and (b) at least one process either goes down or gets stop. Another way of saying this is that of all the processes that arrive at a splitter, some process doesn't go down and some process doesn't go right. By arranging splitters in a grid, this property guarantees that every row or column that gets at least one process gets to keep it—which means that with k processes, no process reaches row k+1 or column k+1.

Here is the actual code for a splitter. We use two atomic registers: a register X, initialized to ⊥, that can hold original names, and a register Y, initialized to false, that holds a single flag bit (the register names are from the paper).

Splitter(id)

1. X ← id
2. if Y = true: go right
3. Y ← true
4. if X = id: stop
5. else: go down

Claim 1

If at least one process completes the splitter, at least one process stops or goes right.

Proof

Let p be the last process to write to X. Then either (a) p sees true in Y and goes right, or (b) p sees false in Y, reads id from X, and stops.

Claim 2

If at least one process completes the splitter, at least one process stops or goes down.

Proof

First observe that if no process ever writes to Y, then no process completes the splitter, because the only way a process can finish the splitter without writing to Y is if it sees true in Y in line 2 (which must have been written by some other process). So if at least one process finishes, at least one process writes Y. Let p be any such process. From the code, having reached line 3, it either stops in line 4 or goes down in line 5.

Claim 3

At most one process stops.

Proof

Let S be the set of processes that reach line 3. The every process in S reads Y before any process in S writes Y. It follows that every process in S writes X before any process in S reads X. If some process p is not the last process in S to write X, it will not see its own id, and will not stop.²

7.2. Splitters in a grid

Now build a k-by-k grid of splitters, arranged as rows 0..k-1 and columns 0..k-1, and assign a name from the range 0..k²-1 to each splitter. (Moir and Anderson assign k⋅r+c to the splitter in row r and column c.) To obtain a name, a process starts at (r,c) = (0,0), and repeatedly executes the splitter at its current position (r,c). If the splitter returns right, it moves to (r,c+1); if down, it moves to (r+1,c); if stop, it stops, and returns the name of its current splitter. We'll show below that a k-by-k grid is enough: no process goes past the end of the grid.

We say that a process reaches row r if it ever runs a splitter in row r, and similarly for reaching column c.

Claim 4

The number of processes that reach row r+1 is either zero or at most one less than the number of processes that reach row r.

Proof

Another way to phrase the claim is that if at least one process reaches row r, at least one process stays there. Suppose some process reaches a splitter at (r,c). Then by Claim 1, at least one process at (r,c) stops or goes right. If it stops, we are done. If it doesn't, use induction on c to show that at least one process eventually stops or goes right until it reaches (r,k-1). In either case at least one process doesn't go down, proving the claim.

Claim 5

The number of processes that reach column c+1 is either zero or at most one less than the number of processes that reach column c.

Proof

Use the same proof as for Claim 4, replacing rows with columns and using Claim 2 instead of Claim 1.

Iterating the preceding claims, the number of processes that reach row r is bounded by k-r for r ≤ k, and similarly the number that reach column c is bounded by k-c for c ≤ k. It follows that no process reaches row k or column k, which is why we don't include these in the grid. (Moir and Anderson give a more sophisticated argument that shows the stronger claim that the number of processes that reach any splitter at (r',c') ≥ (r,c) is bounded by k-(r+c); this shows that only those splitters with r+c < k are actually needed, reducing the number of splitters to k(k+1)/2.) In particular, this means that every process stops somewhere in the grid and adopts a name. By Claim 3, these names are all unique.

The time complexity of this algorithm is O(k): Each process spends at most 4 operations on each splitter, and no process goes through more than 2k splitters. (The actual bound proved in the paper is 4(k-1)).

If we don't know k in advance, we can still guarantee names of size O(k²) by carefully arranging them so that each k-by-k subgrid contains the first k² names. We still have to choose our grid to be large enough for the largest k we might actually encounter.

7.3. Getting to 2k-1 names in bounded space

From before, we have an algorithm that will get 2k-1 names for k processes out of N possible processes when run using O(N) space (for the enormous snapshots). To turn this into a bounded-space algorithm, run Moir-Anderson first to get down to k² names, then run the previous algorithm (in O(k²) space) using these new names as original names.

Since we didn't prove anything about time complexity of the humongous-snapshot algorithm, we can't say much about the time complexity of this combined one. Moir and Anderson suggest using an O(Nk²) algorithm of Borowsky and Gafni to get O(k⁴) time for the combined algorithm. Faster algorithms have probably appeared since then.

---

CategoryDistributedComputingNotes