9.1.1 Subdivisions and manifolds

In Figure 8.6, it is apparent that the single-layer immediate snapshot protocol complex shown is a subdivision of the input complex. Formally, an -process protocol is a subdivision protocol if is a subdivision of and the subdivision carrier map is chromatic (recall Definition 3.4.9). Furthermore, Figure 8.9 suggests that longer executions produce finer subdivisions. A subdivision protocol is a special case of a manifold.

For brevity, we sometimes simply say that two such -simplices can be linked, understanding that every -simplex is linked to itself. Being linked is clearly an equivalence relation. In particular, it is transitive.

Because pseudomanifold with boundary is such a long and awkward term, we will refer to such complexes simply as manifolds in this book, even though, as noted in Remark 9.1.1, this term has a slightly different meaning in other contexts.

An -simplex in is an interior simplex if it is a face of exactly two -simplices, and it is a boundary simplex if it is a face of exactly one. The boundary subcomplex of , denoted , is the set of simplices contained in its boundary -simplices. For an -dimensional simplex , let be the complex containing and all its faces, and the complex of faces of of dimension and lower. (When there is no ambiguity, we will sometimes denote these complexes simply as and .)

Manifolds are preserved by subdivisions: If is an -manifold, then any subdivision of is again an -manifold. Figure 9.2 shows a two-dimensional manifold (with an empty boundary complex).

Indeed, the single-layer protocol complex for three processes in Figure 8.6 is a manifold with boundary, as we shall soon prove. Furthermore, the single-layer protocol complex has a recursive structure of manifolds within manifolds, similar to subdivision protocols, with subdivisions within subdivisions. The boundary of a single-layer three-process layered snapshot protocol complex contains the executions where only two processes participate and itself consists of the union of three manifolds with boundary. For every two processes, the executions where only they participate again form a manifold with boundary (and in fact, a subdivision) and contain executions where only one process participates. An execution where a single process participates is itself a degenerate manifold, consisting of a single vertex. This structure is conveniently captured using carrier maps.

Note that this definition applies to arbitrary protocols, not just layered immediate snapshot protocols.

Here is the operational intuition behind Property 9.1.1. Let be an input simplex, and an -face of where the vertex labeled with process is discarded. Recall from Chapter 8 that is the complex generated by executions starting from where does not participate. Consider the following execution: The processes other than execute by themselves, halting on the vertices of an -simplex . After that, starts running deterministically by itself until it halts. Because there is only one such execution, there is only one -simplex containing .

For layered immediate snapshot protocols, the protocol complexes are subdivisions of the input complex. However, the manifold protocol definition is more general. Consider the manifold protocol shown in Figure 9.3. The input complex is a -dimensional simplex with all its faces. The protocol complex is a -dimensional “punctured torus,” which is a torus with one -simplex removed. The map sends the boundary of the input complex to the boundary of the punctured torus and sends the input complex vertices to the boundary vertices. sends the input complex’s -simplex to the entire protocol complex. (Although we are not aware of any existing computer architecture that supports such a protocol, it is nevertheless a well-defined mathematical object.)

Except for layered immediate snapshots, few of the protocol complexes that arise naturally in the study of distributed computing are manifolds. Nevertheless, we start with the study of manifold protocols because the insights they provide will ease our approach to more complicated models.

9.1.2 Composition of manifold protocols

In this section we prove that the composition of two manifold protocols is again a manifold protocol. In Section 9.2 we will see that any single-layer immediate snapshot protocol is a manifold protocol. Any multilayer protocol is therefore a manifold protocol, since it is the composition of single-layer manifold protocols.

We saw in subsection 4.2.4 that protocols compose in a natural way: If and are two protocols where the protocol complex for the first is contained in the input complex for the second, then their composition is the protocol , where . Informally, the processes first participate in the first protocol, and then they participate in the second, using their final views from the first as inputs to the second.

We now proceed with the proof that is a manifold protocol whenever both and are manifold protocols. Following Definition 9.1.4, we must show that

To prove that for any -simplex of the subcomplex is a manifold, we first need to prove that is strongly connected: Any two -simplices can be connected by a sequence of -simplices in which each pair of consecutive simplices has a common -dimensional face.

Now that we have seen that is strongly connected, we need to check the status of the complex’s -simplices.

It remains to show that the protocol map commutes with the boundary operator

for all .

A simple inductive argument yields:

9.2.1 Properties of single-layer protocol complexes

A single-layer immediate snapshot execution is a sequence

where is the initial configuration, step is a set of active processes that execute concurrent immediate snapshots, and each process appears at most once in the schedule .

When a process participates in step , its immediate snapshot returns the states of processes that participated in and in earlier steps. The process states in the final configuration of an execution satisfy the following properties, where is ’s final state.

Consider all 1-layer executions starting in an initial configuration , where every processes appears exactly once in the schedule. Figure 9.5 combines Figures 4.4 and 8.6. It shows a 3-process example with initial process states , and , respectively, for , and . Thus, , which we write as to avoid clutter. Steps are shown as arrows, and the new value is shown only when a process state changes. Recall from Chapter 8 that the execution at the top right is the execution where , and take steps sequentially:

where

At the bottom left is the fully concurrent execution where all three processes take steps together:

where . At the top left is the execution where takes a step, followed by a step by :

where

When do the final configurations of two executions differ only in the state of a single process? Consider the preceding fully sequential execution, where is alone in a step. If we want to change its final state without modifying the state of any other process, the only choice is to move it to the next step, resulting in the top-left execution:

We cannot move to an earlier step because doing so would change the final states of that step’s processes.

What if we want to modify the final state of in the fully concurrent execution? That process is alone in the last step, so no other process sees its initial state. cannot be moved because there is no other execution where have the same final states. Indeed, as far as are concerned, the execution could have ended without participating.

In summary, if in an execution the state of process is seen by some other process, then either appears alone in a step, which is not the last one, or else appears together with other processes in a step. In either case, we can modify the final state of without modifying the final states of the others. In the first case, is moved to the next step; in the second case, is removed from its step and placed alone in a new step immediately before its old one. Finally, if is not seen by other processes in an execution, it is alone in the last step, and ’s state cannot be changed without affecting the others. The next lemma states this property formally.

9.2.2 One-layer protocol complexes are manifolds

When a process takes an immediate snapshot in step , ’s view is the face of the input simplex whose vertices are colored by the processes that participated in the same or earlier steps. For input -simplex , the set of layered executions defines a subdivision of , the standard chromatic subdivision (see Figure 9.5). Each vertex in this subdivision is a pair , where is the name of process taking the steps, and , the result of its snapshot, is a face of the input simplex . In this chapter, we will not prove that is a subdivision, only that it is a manifold. A proof that is actually a subdivision requires more advanced tools and is postponed to Chapter 16.

Figure 9.5 shows the standard chromatic subdivision of an input simplex for three processes, highlighting the simplices corresponding to certain schedules. Informally, we can see that this complex is a manifold.

First we show that is strongly connected. Each simplex in corresponds to a particular layered execution. We proceed by “perturbing” executions so that only one process’s view is changed by each perturbation. First we show that any execution can be linked to a sequential execution in which only one process is scheduled during each step. Next we show that any sequential execution can be linked to the unique fully concurrent execution in which all processes are scheduled in a single step. In this way, any simplex can be linked to the fully concurrent simplex, and any two simplices can be linked to each other.

Lemmas 9.2.5 and 9.2.6 imply the following:

Finally, this corollary and Lemma 9.2.4 imply the main result of this section.

9.3.1 Sperner’s lemma

Before we turn our attention to set agreement, we provide a statement of the classical Sperner’s lemma for manifolds. We provide a proof for completeness and because this lemma is so important. The proof consists of a simple counting argument that perfectly illustrates the beauty of combinatorial topology, as argued in Chapter 3: Deep, powerful properties of spaces made up of simple pieces can be characterized by counting. Readers uninterested in the proof may read the statement of the lemma and skip to the next subsection.

Recall that an -labeling of a complex is a simplicial map , where is an -simplex. (We use the same name for a simplex and the complex that consists of the simplex and all its faces.) We say that sends a simplex onto if every vertex in is the image of a vertex in . If and have the same dimension and maps onto so that each vertex of is assigned a distinct color, then we say that is properly colored.

To state Sperner’s lemma in our notation, let be equal to the -simplex for a set of names . We then take and its faces to be an input complex. Sperner’s lemma is usually stated in terms of a subdivision of , but the combinatorial proof requires only the manifold property. Thus, instead of a subdivision of , consider a manifold protocol, .

A Sperner coloring of is a labeling that satisfies the properties illustrated in the left-hand complex of Figure 9.4. Here is 2. Choose three colors, say, the names of . The three “corners” of the subdivision are colored with distinct colors. In a Sperner coloring, the interior vertices on each boundary connecting any two corners are colored arbitrarily using only the colors from those two corners, and the interior vertices in each 2-simplex are colored arbitrarily using only colors from those three colors. Sperner’s lemma states that no matter how the arbitrary coloring choices are made, there must be an odd number of 2-simplices that are properly colored (with all three colors). In particular, there must be at least one.

More formally, consider , the identity carrier map from to itself: For each , is equal to the complex , consisting of and all its faces. The labeling is a Sperner coloring if is carried by . Namely, for each ,

Sperner’s lemma says, in particular, that there exists no Sperner’s coloring .

The proof follows from an inductive application of a rather surprising property: For an -dimensional manifold, the number of properly colored -simplices on the boundary can reveal something about the number of properly colored -simplices in the interior.

First, we recall a simple lemma from graph theory. Recall that a graph is a 1-dimensional complex given by a set of vertices and a set of edges . The degree of a vertex, , is the number of edges that contain .

9.3.2 Application to set agreement

The set validity task is set agreement without the requirement that at most, distinct values may be decided. The validity requirement is maintained: Any value decided was some process’s input. Thus, any protocol that solves set agreement also solves set validity. We will prove that any layered protocol solving set validity has an execution whereby different values are decided; hence no set agreement protocol is possible in the layered execution model.

In the set validity task, , each process has one possible input value: its own name. Processes are required to halt with the name of some participating process (perhaps their own). Formally, there is a single input -simplex , and the input complex is , the complex consisting of and its faces. The output complex has vertices of the form for , and a set of vertices is an output simplex if the process names in the first component are distinct. The validity condition means that

Let be a manifold protocol that solves set validity with decision map . The decision map induces a map by projecting onto the output vertex’s value. Suppose that in a vertex of , the decision value is , namely, . Then . Notice that is a Sperner’s coloring of because to solve the validity task, for each input simplex , is sent to a simplex of . Using Sperner’s (Lemma 9.3.1), we obtain that sends onto an odd number of simplices with different output values.

Because every protocol complex in a layered execution model is a manifold complex, we have:

We will discuss again this impossibility result in Chapter 10, where we will consider the connectivity of the protocol complex.

9.4.1 Comparing the powers of tasks

There are various ways of comparing the power of tasks. Here we consider a setting that, although not the most general, is particularly elegant. We say a task implements a task if one can construct a protocol for by composing one or more instances of protocols for , along with one or more layered immediate snapshot protocols. If implements but not vice versa, then we say that is weaker than . Otherwise, they are equivalent.

Recall from subsection 4.2.4 that given two protocols and such that the first’s protocol complex is contained in the second’s input complex, their composition is the protocol , where , which we denote

Now consider tasks and . If their carrier maps are strict, then the tasks can be treated like protocols. Then, task implements task if there exists a protocol equal to the composition

consisting of a sequence of (consecutively compatible) protocols , where each is either an immediate snapshot protocol or else it is , and furthermore, the composed protocol solves . Operationally, the processes go through the protocols in the same order, asynchronously. The processes execute the first protocol, and once a process finishes, it starts the next without waiting for other processes to finish the previous protocol. Each process uses its final view from each protocol as its input value for the next.

Recall that solves if and there exists a chromatic simplicial decision map , satisfying

for all .

9.4.2 Weak symmetry breaking from set agreement

Here we show that one can use a set agreement protocol to implement weak symmetry breaking. Formally, we construct a two-layer protocol, where the first layer is a set agreement protocol and the second an immediate snapshot. The “program logic” resides in the decision map.

For readability, we describe this protocol in terms of a program and flowcharts, but of course this program is just a readable way to specify a protocol complex.

Figures 9.10 and 9.11 shows the control structure and pseudo-code to implement weak symmetry breaking using set agreement. The processes share an -element array of input names, chosen[·], whose entries are initially (Line 3). The processes also share a set agreement protocol instance (Line 4). Each process calls the set agreement object’s decide()method, using its own input name as input, and stores the result in chosen[i](Line 6). The process then takes a snapshot and returns the value if and only if its own input is in the set of inputs chosen by the set agreement protocol (Line 7).

Thus, the protocol with decision map , which corresponds to the code in Figure 9.11, solves weak symmetry breaking.

Notice that for this result, the size of the name space is immaterial.

9.4.3 Weak symmetry breaking does not implement set agreement

For the other direction, we want to show that weak symmetry breaking cannot implement set agreement. We will prove this claim indirectly by constructing a manifold protocol that implements weak symmetry breaking. If weak symmetry breaking could implement set agreement, we could replace the weak symmetry-breaking objects with their manifold task implementations, yielding a manifold protocol for set agreement and contradicting Theorem 9.3.6.

We introduce a new task, , which we call the Moebius task. First we construct the 2-dimensional Moebius task. The input complex is the same as for weak symmetry breaking: Each process starts with a distinct input name.

The task’s output complex is illustrated in Figure 9.12. Take three 2-simplices, , each colored by process names, and define , for , a chromatic subdivision. Abusing notation, let . We call the external face of , (even though it is technically a complex) and , for , the internal faces. We then identify (that is, “glue together”) and , and , and and . The resulting complex is a manifold the boundary complex of which consists of the external faces of the .

Figure 9.13 illustrates the task’s carrier map for the 2-dimensional case. Each process chooses an output vertex of matching color. If a proper subset of the processes participates, they choose to the vertices of a simplex in an external face. If they all participate, they converge to the vertices of any simplex.

Although we have defined the Moebius task as a task, we can also treat it as a protocol, where is the protocol’s input complex, is its protocol complex, and is its (strict) execution carrier map. It is easy to check that the Moebius protocol is a manifold protocol. As such, the Moebius protocol cannot solve 2-set agreement.

As illustrated in Figure 9.14, however, the Moebius protocol can solve weak symmetry breaking. We color each vertex with black and white “pebbles” (that is, 0 or 1 values) as follows: For each central simplex of , color each node black except for the one labeled . For the central simplex of each external face , color the vertices of the central -simplex black. The rest of the vertices are colored white. It is easy to check that (1) no 2-simplex is monochromatic, and (2) the protocol is well defined; namely, there is a corresponding decision map . To solve 3-process weak symmetry breaking, run the Moebius protocol from each 2-simplex in the weak symmetry-breaking input complex .

It follows that the 2-dimensional Moebius task separates weak symmetry breaking and set agreement in the sense that it can implement one but not the other.

Now we generalize this construction to even dimensions. Let . Start with -simplices, , colored with process names, and set . As before, we call the complex the external face of and , for , the internal faces.

The rank of ’s name in a set of process names is the of names in smaller than in that set. For each , let be the map sending the name with rank in to the name with rank .

For each and each , identify the internal face with . Because , and , each -simplex in each internal face lies in exactly two -simplices, so the result is a manifold. (This why this construction works only in even dimensions.)

Let be an input -simplex. The Moebius task’s carrier map carries each proper face of to . It carries itself to all -simplices of .

To show that this task solves weak symmetry breaking, we again color the edges with black and white pebbles so that no simplex is monochromatic and the coloring on the boundary is symmetric. For the central simplex of each , color each node black except for the one labeled . For the central simplex of each external face , color the central -simplex black. The rest are white.

Every -simplex in intersects both a face, either internal or external, and a central -simplex. If intersects an internal face, then the vertices on that face are white, but the vertices on the central simplex are black. If intersects an external face, then it intersects the white node of the central simplex of and a black node of the central simplex of . To solve -process weak symmetry breaking, run the Moebius protocol from each -simplex in the weak symmetry-breaking input complex .

The techniques studied here illustrate how combinatorial and algorithmic techniques complement one another: Combinatorial techniques are often effective to prove impossibility, whereas algorithmic techniques are convenient to show that something is possible.

Note that in the special case when , we have . The -dimensional sphere consists of two points, whereas the -dimensional ball consists of one point, so conditions of (1) and (2) of Definition 9.4.7 specialize precisely to the conditions of Definition 9.1.3.

There is also the following standard topological notion.

The interior of , denoted , is the set of points in that have neighborhoods homeomorphic to an open ball of dimension . The boundary of , denoted , is the complement of in . The boundary points can be characterized as those points that land on the boundary hyperplane of in their respective neighborhoods. If is a manifold of dimension with boundary, then is a manifold of dimension , and is a manifold of dimension .

We note that if is a simplicial manifold with boundary, its geometric realization is a topological manifold with boundary of the same dimension; moreover, the geometric realization of the boundary of is precisely the boundary of . As you can see in Figure 9.2, a 2-dimensional manifold is a kind of a discrete approximation to a surface.

On the other hand, the geometric realization of the pseudomanifold does not have to be a manifold. Perhaps the simplest example is obtained if we take a simplicial -dimensional sphere and glue together the north and south poles,⁴ as shown in Figure 9.15. This space is also called the pinched torus. Clearly, the condition of being a manifold fails at the glued poles, but the condition of being a pseudomanifold is still satisfied since it is a condition for edges and triangles and is untouched by vertices being glued together.