Renaming and Oriented Manifolds
In the -renaming task, each of processes is issued a distinct name taken from a large name space and, after coordinating with one another, each chooses a distinct output name taken from a (much smaller) name space of size . We will be interested in adaptive protocols, where the range of chosen names depends on the number of participating processes. As usual, processes are asynchronous and potentially faulty. Using layered snapshot protocols, for which values of can we devise a protocol that ensures that all nonfaulty processes choose distinct output names?
Adaptive renaming; Index lemma; Oriented manifold; Participating set; Properly colored; Rank-symmetric; Renaming; Weak symmetry breaking
Consider the following air traffic control problem: There are airplanes flying across the Atlantic in all directions. To avoid collisions, we must assign a distinct altitude to each plane, where an altitude is measured in thousands of feet. This task is easy for a centralized air traffic control system: Simply sort the planes by flight number and assign the plane to the altitude.
Suppose, instead, that we want to design a protocol so the planes themselves can coordinate to assign altitudes. We call this problem the renaming task: Each plane starts out with a unique name taken from a large name space (its flight number) and halts with a unique name taken from a smaller name space (its altitude). We are interested in asynchronous protocols because we do not know in advance which planes are participating, and interference may cause communications to be lost or delayed. In real life, of course, planes would communicate by message passing, but for ease of presentation here we will assume they communicate through some kind of shared read-write memory.
How many altitudes are needed to solve renaming? Consider the following simple layered-execution protocol for two planes, and . The planes share an array, initially all . In each layer, each plane takes an immediate snapshot: It writes its flight number to memory and then takes a snapshot of the memory.
Informally, here is why we need three altitudes for two planes. Suppose ’s flight number is less than ’s. If sees ’s flight number, then may or may not have seen ’s flight number. If did not see ’s number, then it will choose 1,000 feet, and if it did see the number, it will choose 3,000 feet, so the only safe choice for is to choose 2,000 feet.
Is it possible for two planes to choose between two altitudes? The answer is no, because if they could, they could solve two-process consensus, which we know to be impossible using layered immediate snapshot or message-passing protocols. For two planes, three altitudes are both necessary and sufficient.
In the -renaming task, each of processes is issued a distinct name taken from a large name space, and after coordinating with one another, each chooses a distinct output name taken from a (much smaller) name space of size . We will be interested in adaptive protocols, where the range of names chosen depends on the number of participating processes. As usual, processes are asynchronous and potentially faulty. Using layered snapshot protocols, for which values of can we devise a protocol that ensures that all nonfaulty processes choose distinct output names?
To rule out trivial solutions, such as having choose output name , the renaming task is index independent, meaning that each knows its name but not its index, which is not part of its state. In any execution, a process’s output name can depend only on its input name, and the way its protocol steps are interleaved with the others’, but not on its index.
12.1 An upper bound: renaming with names
We now present an -process renaming protocol where participating processes choose output names in the range . As noted, processes can compare their names for order and equality, but process indexes are not known to protocols. (That is, “knows” that its name is , but not that its index is .)
12.1.1 An existence proof
We start by restating this task as a combinatorial problem. Let denote the -simplex , and let denote the -simplex . We will construct a subdivision and a rigid simplicial map,
This construction is inductive. For two processes, . is the 1-dimensional chromatic subdivision, consisting of the four vertices
and three edges
The map is defined as follows:
It is easy to check that is rigid and that depends on the order of process names, not their indexes. These definitions are illustrated in Figure 12.1.
Inductively, suppose we have constructed a subdivision and a rigid map
as illustrated for two processes in Figure 12.1. Next, we use the operator to subdivide each -face of . We extend as follows: Let be the unique bijection that preserves order; for vertices of , if , then . Define on by . This subdivision is illustrated in the top of Figure 12.2.
Figure 12.2 Construction of the 3-process renaming subdivision. Apply the 2-process subdivision to each edge of a triangle boundary (top). Add a central triangle, as in the standard chromatic subdivision (middle). Finally, assign name to the central vertex with the largest name, apply the 2-process subdivision to the opposite face, and recursively assign names from 1 to 3 to the remaining face (bottom).
We extend this subdivision of the boundary to a subdivision by introducing a “central” -simplex , just as in the standard chromatic subdivision. The facets of are defined as follows: For each simplex in , let be the face of labeled with complementary process names. The facets of are itself, along with all simplices of the form . See the illustration in the middle of Figure 12.2.
Finally, let be the vertex of labeled with the highest process name. Define to be the relative subdivision of constructed by replacing with . Define , and for each , assign output names starting from and moving “down,”
where is the order-preserving bijection.
Theorem 11.2.1, which is proved earlier in the book, implies that there is a color-preserving simplicial map
for some , which translates directly into an -round protocol. In the next section, we give an explicit construction for this protocol.
12.1.2 An explicit protocol
We leave it as an exercise (12.1) to show how to construct a single-layer immediate snapshot participating set protocol. We will use a slight variation of this task, called tagged participating set: Each process has a tag value as input, and the sets returned include the names of the processes with matching tags only.
Figure 12.3 shows the protocol that corresponds to the previous section’s subdivision construction. Output names are allocated either top-down or bottom-up, depending on whether we assign the next output name from the high or low end of the range of unassigned output names. Each recursive call to the tagged participating set protocol takes the history of prior participating sets, so processes observe only other processes with the same history.
As before, denote distinct participating sets, and denotes the set observed by . If , the process with the highest name, observes the largest participating set, that is, if , then chooses output name and halts. Every other such that proceeds as if had chosen and joins a recursively called protocol to choose names bottom-up from the range .
The processes that observe , the second-largest participating set, act as if they are the only participants. If the process with the largest name in observes , then it chooses and halts. The others proceed as if that process had chosen the output name and recursively call a protocol to choose names bottom-up in the range . In this way, the range of names is recursively broken up.
We will now show that for some values of , this -renaming protocol is the best one can do using asynchronous read-write memory.
12.2 Weak symmetry breaking
Recall from Chapter 9 that in the weak symmetry-breaking (WSB) task, processes have fixed input values and binary output values. In every execution in which all processes participate, at least one process decides 0 and at least one process decides 1. Like renaming, any protocol that implements WSB must be index-independent. We now show that weak symmetry breaking is equivalent to (non-adaptive) -renaming: Any protocol for one can be transformed to a protocol for the other. Suppose we are given a “black-box” index-independent protocol that solves -renaming. The processes run a -renaming protocol, and each process decides the parity (value mod 2) of its output name. If all processes participate, at least one must decide 0 and at least one must decide 1, because the range does not contain even or odd values.
Here is how to transform a “black-box” solution to weak symmetry breaking into a protocol for non-adaptive -renaming. First, each process executes the weak symmetry-breaking protocol and uses its binary output to choose between two instances of the -renaming protocol of Figure 12.3. The first instance assigns output names moving up from 0, and the second assigns output names moving down from . The processes that decide value 0 join the first renaming protocol, and each is assigned a name in the range . The other processes join the second protocol, and each is assigned an output name in the range . Each process in the second group subtracts this name from , yielding an output name in the range . The ranges of names chosen by the two groups do not overlap.
It follows that instead of deriving a lower bound for adaptive or non-adaptive -renaming, it is enough to derive a lower bound for weak symmetry breaking. Here is our strategy. If there is a wait-free layered immediate snapshot protocol for weak symmetry breaking, then we know from the proof of Theorem 11.2.1 that there is a layered read-write protocol and a color-preserving simplicial map
carried by , the input-output relation defining weak symmetry breaking. The map , however, just maps each vertex to a binary value, so we can think if it simply as a binary coloring , with no monochromatic -simplices (that is, -simplices in which all vertices are mapped to the same value). Moreover, the protocol is index-independent, implying that the coloring is symmetric on the boundary of .
To show a lower bound, we need an analog to Sperner’s lemma for binary colorings. Under what circumstances is it impossible to construct a symmetric binary coloring for a subdivided -simplex that admits no monochromatic -simplices?
12.3 The index lemma
We now prove a combinatorial lemma that will help us understand weak symmetry breaking. An -coloring of a complex is a map from the vertices of to :
A simplex is properly colored by if is rigid: It maps each vertex of to a distinct vertex of . A complex is chromatic if it has a coloring
An orientation of a simplex is given by a sequence of its vertices, up to the action of even permutations of that sequence.1 For example, we use the notation to denote the orientation given by the sequence and its even permutations, such as .
Any simplex has two possible orientations. An orientation of an -simplex induces an orientation on its -faces: If is oriented , then has the induced orientation if is even, where a circumflex ( ) denotes omission, and the opposite orientation if is odd. As illustrated in Figure 12.4, it is natural to think of an oriented edge as an arrow and an oriented triangle as being oriented clockwise or counterclockwise.
A oriented manifold is an -manifold with boundary together with an orientation for each -simplex with the property that every two -simplices that share an -face induce opposite orientations on their common face. Not all manifolds are orientable, but we here we will be concerned with subdivided simplices, which are orientable (see Figure 12.5). Henceforth, will be an oriented chromatic manifold with boundary.
We say that an -simplex is positively oriented if the sequence is an even permutation of the sequence , and it is negatively oriented otherwise. Positive orientation is denoted by and negative orientation by . The positive and the negative orientations alternate as we pass through each internal -simplex. For each -simplex on the boundary of , there is a unique such that . Define .
We will use the following facts about subdivisions.
Now consider together with a coloring , not necessarily proper. In other words, the complex now has two colorings: the proper coloring , and an arbitrary coloring . Henceforth, when we say a simplex of is properly colored, we mean properly colored by . A properly colored simplex in is counted by orientation as follows: Index the vertices of in the order of their colors: such that . If belongs to the orientation induced by , then , and otherwise . If is not properly colored, then .
For each , consider the set of boundary -simplices colored properly with values from . These simplices, too, can be counted by orientation, with the definition of the corresponding quantity repeating verbatim that of . Index the vertices of in the order of their colors: such that . If belongs to the orientation induced by , then define , and otherwise define . If is not properly colored with values from , then .
Content and index are related as follows.
Because a manifold’s content is determined by its boundary, two colorings that agree on the boundary have the same content.
Consider the special case where is a subdivided simplex. Corollary 12.3.6 implies that when counting properly colored simplices by orientation, we can “recolor” the interior vertices to any convenient color.
12.4 Binary colorings
Let be a manifold with boundary with a proper coloring and a binary labeling . Define a new coloring by setting
for all . The following is immediate:
Because of Lemma 12.4.1, we can use the content to count by orientation monochromatic -simplices under . Here we note that if is -monochromatic under for some , then it is counted as by orientation. The Index Lemma 12.3.5 implies the next statement.
We can therefore assume, without loss of generality, that for every not on the boundary of . We now show that the content of the -simplices containing these internal all-0 vertices is .
We will use to denote the coloring that assigns 0 to every vertex, and similarly for .
Let , the central simplex, be the simplex of that represents the execution in which all processes execute in lock-step (together) for rounds. We take as the orientation of and induce uniquely an orientation on the entire . We take that orientation as standard; see Figure 12.6.
An internal simplex of is one that contains no boundary vertices.
12.5 A lower bound for -renaming
We now show that if is a prime power, weak symmetry breaking, and hence -renaming, is impossible. We argue by contradiction. Assume we have an index-independent wait-free protocol for weak symmetry breaking.
Assume is an -simplex. For all , let denote the rank-preserving bijection, and let denote the affine isomorphism of the corresponding boundary simplices and of induced by the map .
The following is a useful lemma about rank-symmetric subdivisions.
Recall that the Index lemma 12.3.5 ensures that we can assume without loss of generality that for any vertex not in . Since every -simplex in contains at least one such vertex, has no -monochromatic simplices, so we can compute the number by orientation of monochromatic -simplices in simply by computing the number by orientation of -monochromatic simplices.
12.6 Chapter notes
The renaming algorithm presented here is due to Borowsky and Gafni . The recursive formulation of Figure 12.3 is due to Gafni and Rajsbaum . An earlier and less efficient algorithm is due to Attiya et al. . The connection between renaming and weak symmetry breaking is due to Gafni, Herlihy and Rajsbaum . The renaming lower bound is due to Castañeda and Rajsbaum [31,32]. Attiya and Paz  prove the weak symmetry-breaking impossibility applying the Index Lemma directly on executions. There is an overview of renaming in shared memory systems by Castañeda, Rajsbaum and Raynal .
It turns out that if is not a prime power, then there is an index-independent wait-free read-write protocol for -renaming, as shown by Castañeda and Rajsbaum [31,33]. An algebraic topology proof is given by Castañeda, Herlihy, and Rajsbaum  and a more direct upper-bound construction by Attiya et al. ; see also Kozlov .
1An even permutation is one that can be constructed by exchanging the positions of adjacent elements an even number of times.