Chapter 12. Renaming and Oriented Manifolds – Distributed Computing Through Combinatorial Topology

Chapter 12

Renaming and Oriented Manifolds

Abstract

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?

Keywords

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.

• If a plane sees only its own flight number, it chooses altitude 1,000 feet.

• If a plane sees both flight numbers, it compares them.

• If its own number is less than the other’s, it chooses altitude 2,000.

• Otherwise, it chooses altitude 3,000.

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.

Figure 12.1 The 2-process subdivision Rename. Vertex color indicates each process’s input name, and vertex number indicates its choice of output name.

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.

Lemma 12.1.1

Every facet of is assigned distinct names in the range .

Proof

We argue by induction on . The claim for holds by inspection.

Assume the claim holds for . By the induction hypothesis, for , assigns each -simplex in distinct names in the range .

By construction, assigns distinct names in the range to each simplex in , and it assigns to , so it assigns distinct names in the range to each simplex in .

Let be an -simplex in , and let be an -face of labeled with the complementary process names. By construction, is a facet of , and every facet other than can be expressed in this way. By the induction hypothesis, assigns to the vertices of distinct names in the range . The greatest name that can be assigned to is , and the least is

Since the ranges assigned to and do not overlap, the facet is assigned distinct names in the range .  

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 will use as a building block the participating set task, where each process has its own name as its only possible input and has a set of process names as output, where:

• ,

• For all , either or vice versa, and

• For all , if , then .

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.

Lemma 12.1.2

Let be the distinct sets returned by a participating set protocol, and let denote the set returned to . We claim that observes the first participating set in which it appears: If , then .

Proof

Left as Exercise 12.3.  

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.

Figure 12.3 Renaming protocol.

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.

Theorem 12.1.3

The protocol of Figure 12.3 is wait-free.

Proof

In each round, the active process with the highest name chooses a name and halts, so every process finishes in rounds.  

Theorem 12.1.4

The protocol of Figure 12.3 assigns distinct output names in the range to each of participants.

Proof

We argue by induction on . When , the claim is clear from inspection.

For the induction hypothesis, assume that the protocol assigns top-down distinct names in the range , for all . By Lemma 12.1.2, the processes that observe , the largest set, are exactly the processes in . There are two cases to consider. First, if all processes observe , then the process with the highest name drops out with , and the remaining processes choose names bottom-up, starting at . By the induction hypothesis, they choose distinct names in the range .

Otherwise, if some processes observe , then at most processes choose names bottom-up starting at . By the induction hypothesis, if they were choosing top-down, they would choose names in the range . But because they are choosing bottom-up starting at , the least name they can choose is

The largest name that can be chosen by the processes not in is , so these ranges do not overlap.  

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

that properly colors every simplex of .

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 .

Mathematical Note 12.3.1

Formally, the group of all even permutations acts on the set of all ordered sequences of vertices, there are two orbits, and an orientation is a choice of an orbit.

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.

Figure 12.4 Oriented simplices and their boundaries.

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.

Figure 12.5 Oriented 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.

Fact 12.3.2

If is a chromatic subdivision of , then is an orientable manifold, as is , for any . An orientation of induces an orientation of .

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 .

Definition 12.3.3

The content of in , denoted , is the number of simplices properly colored by , counted by orientation:

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 .

Definition 12.3.4

For each , the index of , denoted by , is the number of -simplices of its boundary complex , properly colored with values from , counted by orientation.

Content and index are related as follows.

Lemma 12.3.5

Index Lemma

If is an oriented manifold colored by , then for each we have the identity

Proof

Fix . Suppose consists of a single simplex (and its faces). If is properly colored, then . For each is properly colored with values from , with induced orientation , so , and .

Suppose instead that is not properly colored, so . Clearly if has no properly colored -faces. Suppose instead that at least one -face of is properly colored with values from . Because does not appear in the coloring, another value must appear twice, so there are exactly two -faces of properly colored with values from . Index the vertices of such that . and have the same coloring but opposite induced orientations, so their contributions to cancel, yielding .

Now consider an arbitrary manifold with boundary . Consider the following sum:

(12.3.1)

Each internal -simplex is counted twice in (12.3.1), and it is counted with opposite orientations, so these contributions cancel out. On the other hand, each boundary -simplex is counted once, so we have

(12.3.2)

We have seen that , so

(12.3.3)

It follows from (12.3.2) and (12.3.3) that .  

Because a manifold’s content is determined by its boundary, two colorings that agree on the boundary have the same content.

Corollary 12.3.6

If and are colorings of such that for all , then .

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

Although the Index Lemma 12.3.5 and Corollary 12.3.6 are concerned with colorings that take on values, we can extend these results to reason about binary colorings as well.

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:

Lemma 12.4.1

An -simplex of is monochromatic under if and only if it is properly colored under .

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.

Corollary 12.4.2

If and are binary colorings that agree on , then the number of monochromatic simplices of counted by orientation is the same in both.

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.

Lemma 12.4.3

Assume is an -simplex and is the -fold standard chromatic subdivision of . Then we have and .

Proof

We first calculate that . For , we note that is a subdivision of a -simplex into an odd number of simplices. These simplices are oriented alternating, and the leftmost simplex is positively oriented. Hence there is one more simplex oriented positively than negatively, and hence the total sum is ; see Figure 12.7.

Having verified the base, we can now use induction on . For the induction step, assume that when . By the Index lemma 12.3.5, we have

To see that note that the all-1 coloring “rotates” the process names, sending to . This permutation is even if and only if is even, so orientations are multiplied by .  

Figure 12.6 Standard orientation for Ch . Here there are three processes, so , and one round of execution, so . The orientation of the central simplex marked is therefore .

Figure 12.7 Orientation for a 1-dimensional subdivision.

An internal simplex of is one that contains no boundary vertices.

Lemma 12.4.4

If all internal vertices are colored 0, then the content of the internal simplices is .

Proof

Let be the binary coloring that assigns to every vertex on the boundary and to every internal vertex. By construction, is just the content of the internal simplices, since all the other -simplices are not monochromatic. Because agrees with on the boundary, .  

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 .

Definition 12.5.1

A binary coloring is called rank symmetric if, for any choice of and as above, the map induces an isomorphism of the subdivisions , and, in addition, is invariant with respect to . Formally, the last condition says that for every , we have .

The following is a useful lemma about rank-symmetric subdivisions.

Lemma 12.5.2

Let be a simplex in the subdivided boundary . For any set such that , there is an orientation-preserving bijection between the following two sets of -simplices of :

Proof

Let be, as above, the central simplex of . Define a flip to be the operation of moving from one -simplex to another by replacing a single vertex. For example, a flip might go from to , where . If we can get from to in a single flip, then and have opposite orientations. We can characterize a sequence of flips by the names of the vertices replaced: A sequence of flips replaces the vertex whose ID is at step . Two -simplices have the same orientation if and only if we can get from one to the other through an even sequence of flips.

Assume that is a face of an -simplex . We can get from to by a sequence of flips: . Because is symmetric, we can use a reversed, symmetric sequence of flips to get from to an -simplex, which we call . It takes a total of flips to get from to , so they have the same orientation in . Clearly, is an -simplex such that , and the above procedure yields a bijection.  

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.

Lemma 12.5.3

The number of monochromatic -simplices in , counted by orientation, is

for integers .

Proof

Take . By Lemma 12.4.4, the internal simplices contribute to the content. Let , and suppose has 0-monochromatic -simplices counted by orientation. There are such faces, and by Lemma 12.5.2, they have the same contributing to the count of 0-monochromatic -simplices of .  

Now we make use of the following fact from number theory.

Fact 12.5.4

The integers in the set

have a common factor if and only if is a prime power.

Theorem 12.5.5

If is a prime power, then there is no index-independent wait-free read-write protocol for -renaming.

Proof

If there is a protocol for weak symmetry breaking, then there is an iterated standard chromatic subdivision that has a binary coloring with no monochromatic -simplices. There is therefore a binary coloring for with no 0-monochromatic -simplices. Because is symmetric, however, the number of 0-monochromatic -simplices it contains is

(12.5.1)

By Fact 12.5.4, if is a prime power, then these binomial coefficients share a common factor, and this number cannot be zero.  

12.6 Chapter notes

The renaming algorithm presented here is due to Borowsky and Gafni [24]. The recursive formulation of Figure 12.3 is due to Gafni and Rajsbaum [68]. An earlier and less efficient algorithm is due to Attiya et al. [9]. The connection between renaming and weak symmetry breaking is due to Gafni, Herlihy and Rajsbaum [69]. The renaming lower bound is due to Castañeda and Rajsbaum [31,32]. Attiya and Paz [15] 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 [34].

The version of the Index Lemma we used is a restatement of Corollary 2 by Fan [54] using our notation. For a simple description of this lemma in dimension see Henle [77, pp. 46-47].

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 [125] and a more direct upper-bound construction by Attiya et al. [11]; see also Kozlov [102].

Exercise 12.6 and 12.7 are inspired by work of Moir and Anderson [117].

12.7 Exercises

Exercise 12.1

Give a single-round immediate snapshot protocol for the tagged participating set task defined in Section 12.1.2.

Exercise 12.2

Prove Fact 12.5.4.

Exercise 12.3

Prove Lemma 12.1.2.

Exercise 12.4

Show that if a manifold with boundary has an orientation, then there are exactly two possible orientations.

Exercise 12.5

Recall that the testAndSet() operation atomically swaps true with the contents of a memory location. Devise a wait-free -renaming protocol using testAndSet() objects. How small can you make ?

Exercise 12.6

An MA-box is named after its inventors, Mark Moir and James Anderson. It provides a single method, visit(), which returns one of three values: STOP, DOWN, or RIGHT. Figure 12.8 shows the code for visit(). The MA-Box object has two fields, last, initially , and goRight, initially false. These fields can be read and written by multiple processes. When a process calls visit(), it stores its own name in the last field. If goRight field is true, it returns RIGHT. Otherwise, it rereads last and if its name is still present, it returns STOP; otherwise it reruns DOWN.

Prove that if threads call visit(),

• At most, one thread gets the value STOP.,

• At most, threads get the value DOWN, and

• At most, threads get the value RIGHT.

Note that the last two proofs are not symmetric.

Exercise 12.7

Arrange MA-box objects in a triangular matrix, where each MA-Box is given an integer name as shown in Figure 12.9. Each thread starts by visiting MA-Box zero. If it gets STOP, it stops. If it gets RIGHT, it visits 1, and if it gets DOWN, it visits 2. In general, if a thread gets STOP, it stops. If it gets RIGHT, it visits the next MA-Box on that row, and if it gets DOWN, it visits the next MA-Box in that column. Each thread takes the name of the MA-Box object where it stops.

Prove that MA-Boxes can be used to solve -renaming.

• Prove that each thread eventually stops at some MA-Box object.

• How many MA-Box objects do you need in the array if you know in advance a bound on the number of threads?

Figure 12.8 Code for MA-Box.

Figure 12.9 Array layout for MA-Box objects.


1An even permutation is one that can be constructed by exchanging the positions of adjacent elements an even number of times.