Connectivity
Abstract
In Chapter 9, we considered models of computation in which, for any protocol 
and any input simplex 
, the subcomplex 
is a manifold. We saw that any such protocol cannot solve 
-set agreement for 
. In this chapter, we investigate another important topological property of the complex 
: having no “holes” in dimensions 
and below, a property called 
-connectivity. We will see that if every 
is 
-connected, then 
cannot solve 
-set agreement. We will see later that there are natural models of computation for which protocol complexes are not manifolds, but they are 
-connected for some 
. We will also use this notion of connectivity in later chapters to characterize when protocols exist for certain tasks.
Keywords
Connected; Critical configuration; Nerve complex; Nerve graph; Nerve lemma; Path connected; Reachable complex
In Chapter 9, we considered models of computation for which for any protocol 
and any input simplex 
, the subcomplex 
is a manifold. We saw that any such protocol cannot solve 
-set agreement for 
. In this chapter, we investigate another important topological property of the complex 
: having no “holes” in dimensions 
and below, a property called 
-connectivity. We will see that if every 
is 
-connected, then 
cannot solve 
-set agreement. We will see later that there are natural models of computation for which protocol complexes are not manifolds, but they are 
-connected for some 
. We will also use this notion of connectivity in later chapters to characterize when protocols exist for certain tasks.
10.1 Consensus and path connectivity
We start with the familiar, 1-dimensional notion of connectivity and explore its relation to the consensus task.
Recall from Section 8.3.1 that in the consensus task for 
processes, each process starts with a private input value and halts with an output value such that (1) all processes choose the same output value, and (2) that value was some process’s input.
Here we consider the consensus task 
with an arbitrary input complex. In other words, instead of requiring that the input complex contain all possible assignments of values to processes, we allow 
to consist of an arbitrary collection of initial configurations. There are particular input complexes for which consensus is easily solvable. An input complex is said to be degenerate for consensus if every process has the same input in every configuration. Consensus is easy to solve if the input complex is degenerate; each process simply decides its input. We will see that if a protocol’s carrier map takes each simplex to a path-connected subcomplex of the protocol complex, then that protocol cannot solve consensus for any nondegenerate input complex.
Informally, consensus requires that all participating processes “commit” to a single value. Expressed as a protocol complex, executions in which they all commit to one value must be distinct, in some sense, from executions in which they commit to another value. We now make this notion more precise.
Recall from Section 3.5.1 that a complex 
is path-connected if there is an edge path linking any two vertices of 
. In the next theorem, we show that if a protocol carrier map satisfies a local path-connectivity condition, it cannot solve consensus for nondegenerate input complexes.
Theorem 10.1.1
Let 
be a nondegenerate input complex for consensus. If 
is an 
-process consensus task, and 
is a protocol such that 
is path-connected for all simplices 
in 
, then 
cannot solve the consensus task 
.
Proof
Assume otherwise. Because 
is not degenerate, it contains an edge 
such that 
. (That is, there is an initial configuration where two processes have distinct inputs.) By hypothesis, 
is path-connected, and by Proposition 3.5.3, 
is path-connected as well and lies in a single path-connected components of 
. But each path-connected component of the consensus output complex 
is a single simplex whose vertices are all labeled with the same output value, so 
is contained in one of these simplices, 
.
Because 
is a carrier map, 
. Similarly, 
. It follows that 
and 
are both vertices of 
; hence they must be labeled with the same value.
Because the protocol 
solves the task 
is a vertex of 
, and 
is a vertex of 
. Consensus defines 
to be a single vertex labeled with 
, and therefore 
is also labeled with 
. By a similar argument, 
is labeled with 
. It follows that 
and 
must be labeled with distinct values, a contradiction. 
This impossibility result is model-independent: It requires only that each 
be path-connected. We will use this theorem and others like it to derive three kinds of lower bounds:
• In asynchronous models, the adversary can typically enforce these conditions for every protocol complex. For these models, we can prove impossibility: Consensus cannot be solved by any protocol.
• In synchronous models, the adversary can typically enforce these conditions for 
or fewer rounds, where 
is a property of the specific model. For these models, we can prove lower bounds: Consensus cannot be solved by any protocol that runs in 
or fewer rounds.
• In semisynchronous models, the adversary can typically enforce these conditions for every protocol that runs in less than a particular time 
, where 
is a property of the specific model. For these models, we can prove time lower bounds: Consensus cannot be solved by any protocol that runs in time less than 
.
In the next section, we show that layered immediate snapshot protocol complexes are path-connected.
10.2 Immediate snapshot model and connectivity
We now show that if 
is a layered immediate snapshot protocol, then 
is path-connected for every simplex 
.
10.2.1 Critical configurations
Here we introduce a style of proof that we will use several times, called a critical configuration argument. This argument is useful in asynchronous models, in which processes can take steps independently. As noted earlier, we can think of the system as a whole as a state machine where each local process state is a component of the configuration. Each input 
-simplex 
encodes a possible initial configuration, the protocol complex 
encodes all possible protocol executions starting from 
, and each facet of 
encodes a possible final configuration. In the beginning, all interleavings are possible, and the entire protocol complex is reachable. At the end, a complete execution has been chosen, and only a single simplex remains reachable. In between, as the execution unfolds, we can think of the reachable part of the protocol complex as shrinking over time as each step renders certain final configurations inaccessible.
We use simplex notation (such as 
) for initial and final configurations, since they correspond to simplices of the input and protocol complexes. We use Latin letters for transient intermediate configurations (
).
We want to show that a particular property, such as having a path-connected reachable protocol complex, that holds in each final configuration also holds in each initial configuration. We argue by contradiction. We assume that the property does not hold at the start, and we maneuver the protocol into a critical configuration where the property still does not hold, but where any further step by any process will make it hold henceforth (from that point on). We then do a case analysis of each of the process’s possible next steps and use a combination of model-specific reasoning and basic topological properties to show that the property of interest must already hold in the critical configuration, a contradiction.
Let 
be an input 
-simplex, 
, and let 
be a configuration reached during an execution of the protocol 
starting from 
. A simplex 
of 
is reachable from 
if there is an execution starting from configuration 
and ending in final configuration 
. The subcomplex of the protocol complex 
consisting of all simplices that are reachable from intermediate configuration 
is called the reachable complex from 
and is denoted 
.
Definition 10.2.1
Formally, a property 
is a predicate on isomorphism classes of simplicial complexes. A property is eventual if it holds for any complex consisting of a single 
-simplex and its faces.
For brevity, we say that a property 
holds in configuration 
if 
holds for 
, the reachable complex from 
.
Definition 10.2.2
A configuration 
is critical for an eventual property 
if 
does not hold in 
but does hold for every configuration reachable from 
.
Informally, a critical configuration is a last configuration where 
fails to hold.
Lemma 10.2.3
Every eventual property 
either holds in every initial configuration or it has a critical configuration.
Proof
Starting from an initial configuration where 
does not hold, construct an execution by repeatedly choosing a step that carries the protocol to another configuration where 
does not hold. Because the protocol must eventually terminate in a configuration where 
holds, advancing in this way will eventually lead to a configuration 
where 
does not hold, but every possible next step produces a configuration where 
holds. The configuration 
is the desired critical configuration. 
10.2.2 The nerve graph
We need a way to reason about the path connectivity of a complex from the path connectivity of its subcomplexes.
Definition 10.2.4
Let 
be a finite index set. A set of simplicial complexes 
is called a cover for a simplicial complex 
, if 
.
Definition 10.2.5
The nerve graph 
is the 1-dimensional complex (often called a graph) whose vertices are the components 
and whose edges are the pairs of components 
where 
, which have non-empty intersections.
Note that the nerve graph is defined in terms of the cover, not just the complex 
.
The lemma that follows is a special case of the more powerful nerve lemma (Lemma 10.4.2) used later to reason about higher-dimensional notions of connectivity.
Lemma 10.2.6
If each 
is path-connected and the nerve graph 
is path-connected, then 
is also path-connected.
Proof
We will construct a path between two arbitrary vertices 
and 
for 
. By hypothesis, the nerve graph contains a path 
, for 
, where 
.
We argue by induction on 
, the number of edges in this path. When 
are both in 
, and they can be connected by a path because 
is path-connected by hypothesis.
Assume the claim for paths with fewer than 
edges, and let 
. By construction, 
is non-empty. Pick a vertex 
in 
. By the induction hypothesis, 
is path-connected, so there is a path 
from 
to 
in 
. By hypothesis, 
is path-connected, so there is a path 
from 
to 
in 
. Together, 
and 
form a path linking 
and 
. 
10.2.3 Reasoning about layered executions
To reason about the connectivity of layered protocol complexes, we need some basic lemmas about their structure. Assume 
is a configuration, 
is a subset of process names, and 
is a protocol. We introduce the following notations:
• Let 
denote the configuration obtained from 
by running the processes in 
in the next layer.
• Let 
denote the complex of executions that can be reached starting from 
; we call 
the reachable complex from 
.
• Let 
denote the complex of executions where, starting from 
, the processes in 
halt without taking further steps, and the rest finish the protocol.
In the special case 
.
These notations may be combined to produce expressions like 
, the complex of executions in which, starting from configuration 
, the processes in 
simultaneously take immediate snapshots (write then read), the processes in 
then halt, and the remaining processes run to completion.
For future reference we note that for all 
, and all configurations 
, we have
(10.2.1)
Recall that each configuration, which describes a system state, has two components: the state of the memory and the states of the individual processes. Let 
and 
be sets of process names, where 
.
Lemma 10.2.7
If 
, then configurations 
and 
agree on the memory state and on the states of processes not in 
, but they disagree on the states of processes in 
.
Proof
Starting in 
, we reach 
by letting the processes in 
take immediate snapshot in a single layer. Each process in 
reads the values written by the processes in 
.
Starting in 
, we reach 
by letting the processes in 
write, then read in the first layer, and we reach 
by then letting the processes in 
but not in 
write, then read in the second layer. Each process in 
reads the values written by the processes in 
, but each process in 
reads the values written by 
.
Both executions leave the memory in the same state, and both leave each process not in 
in the same state, but they leave each process in 
in different states.
Figure 10.1 shows an example where there are four processes, 
, and 
, where 
and 
. The initial configuration 
is shown on the left. The top part of the figure shows an execution in which 
writes 0 to its memory element and then reads the array to reach 
, and then 
writes 1 and reads to reach 
. The bottom part shows an alternative execution in which 
and 
write 0 and 1, respectively, and then read the array to reach 
. 
Figure 10.1 Proof of Lemma 10.2.7: The starting configuration 
is shown on the left, where 
, and each memory element is initialized to 
. Two alternative executions appear at the top and bottom of the figure. The top shows an execution where 
writes and reads first, followed by 
. The bottom shows an execution where 
writes and reads first. In both executions, if we halt the processes in 
, then we end up at the same configuration shown on the right.
Lemma 10.2.8
If 
and 
, configurations 
and 
agree on the memory state and on the states of processes not in 
, but they disagree on the states of processes in 
.
Proof
Starting in 
, we reach 
by letting the processes in 
write, then read in the first layer, and we reach 
by letting the process in 
write, then read in the second layer. Each process in the first layer reads the states written by 
, and each process in the second layer reads the states written by 
. Similarly, starting in 
, we reach 
by first running 
, then 
. Each process in the first layer reads the states written by 
, and each process in the second layer reads the states written by 
. Both configurations agree on the memory state and on states of processes not in 
, but they disagree on the states of processes in 
.
Figure 10.2 shows an example where there are four processes, 
, and 
, where 
and 
. The initial configuration 
is shown on the left. The top part of the figure shows an execution in which 
write 0 and 1, respectively, read the array to reach 
, and then 
writes 2 and reads to reach 
. The bottom part shows an alternative execution in which 
write 0 and 1, respectively, read the array to reach 
, and then 
writes 0 and reads to reach 
. 
Figure 10.2 Proof of Lemma 10.2.8: The starting configuration 
is shown on the left, where 
, and each memory element is initialized to an arbitrary value 
. Two alternative executions appear at the top and bottom of the figure. The top shows an execution where 
writes and reads first, followed by 
. The bottom shows an execution where 
writes and reads first, followed by 
. In both executions, if we halt the processes in 
, then we end up at the same configuration, shown on the right.
Proposition 10.2.9
Assume that 
is a configuration and 
; then we have
where 
, the set of processes that take no further steps, satisfies
Proof
There are two cases. For the first case, suppose 
. For inclusion in one direction, Lemma 10.2.7 states that configurations 
and 
disagree on the states of processes in 
, implying that every execution in 
is an execution in 
where no process in 
takes a step:
For inclusion in the other direction, Lemma 10.2.7 also states that configurations 
and 
agree on the memory and on states of processes not in 
, implying that every execution starting from 
in which the processes in 
take no steps is also an execution starting from 
:
The case 
is settled analogously.
For the second case, suppose 
and 
. For inclusion in one direction, Lemma 10.2.8 states that in 
and 
, the processes in 
have distinct states, implying that every execution in 
is an execution in 
where no process in 
takes a step:
For inclusion in the other direction, Lemma 10.2.8 also states that in 
and 
, the processes not in 
have the same states, as does the memory, implying that every execution starting from 
in which the processes in 
take no steps is also an execution starting from 
or from 
:
10.2.4 Application
For each configuration 
, the reachable complexes 
cover 
, as 
ranges over the non-empty subsets of 
, defining a nerve graph 
. The vertices of this complex are the reachable complexes 
, and the edges are pairs 
, where
We know from Proposition 10.2.9 that
which is non-empty if and only if we do not halt every process: 
.
Lemma 10.2.10
The nerve graph 
is path-connected.
Proof
We claim there is an edge from every nerve graph vertex to the vertex 
. By Proposition 10.2.9,
Because 
, this intersection is non-empty, implying that the nerve graph has an edge from every vertex to 
. It follows that the nerve graph is path-connected. 
Theorem 10.2.11
For every wait-free layered immediate snapshot protocol and every input simplex 
, the subcomplex 
is path-connected.
Proof
We argue by induction on 
. For the base case, when 
, the complex 
is a single vertex, which is trivially path-connected.
For the induction step, assume the claim for 
processes. Consider 
, where 
. Being path-connected is an eventual property, so it has a critical configuration 
such that 
is not path-connected, but 
is path-connected for every configuration 
reachable from 
. In particular, for each set of process names 
, each 
is path connected.
Moreover, the subcomplexes 
cover the simplicial complex 
, and Lemma 10.2.10 states that the nerve graph of this covering is path-connected. Finally, Lemma 10.2.6 states that these conditions ensure that 
is itself path-connected, contradicting the hypothesis that 
is a critical state for path connectivity. 
Theorem 10.2.11 provides an alternate, more general proof that consensus is impossible in asynchronous read-write memory.
10.3 k-Set agreement and 
-connectivity
We consider the 
-set agreement task 
with arbitrary inputs, meaning we allow 
to consist of an arbitrary collection of initial configurations. An input complex is said to be degenerate for 
-set agreement if, in every input configuration, at most 
distinct values are assigned to processes. Clearly, 
-set agreement has a trivial solution if the input complex is degenerate. We will see that if a protocol’s carrier map satisfies a topological property called 
-connectivity, then that protocol cannot solve 
-set agreement for any nondegenerate input complex.
Theorem 10.3.1
Let 
be a nondegenerate input complex for 
-set agreement. If 
is an 
-process 
-set agreement task, and 
is a protocol such that 
is 
-connected for all simplices 
in 
, then 
cannot solve the 
-set agreement task 
.
Proof
Because 
is not degenerate, it contains a 
-simplex 
labeled with 
distinct values. Let 
denote the 
-simplex whose vertices are labeled with the input values from 
, and let 
be its 
-skeleton. Let 
denote the simplicial map that takes every vertex 
to its value in 
. Since each vertex of 
is labeled with a value from a vertex of 
and since the protocol 
solves 
-set agreement, the simplicial map 
is well-defined.
Since the subcomplexes 
are 
-connected for all simplices 
, Theorem 3.7.5(2) tells us that the carrier map 
has a simplicial approximation. In other words, there exists a subdivision 
of 
, together with a simplicial map 
, such that for every simplex 
, we have 
.
The composition simplicial map
can be viewed as a coloring of the vertices of 
by the vertex values in 
. Clearly, for every 
, the set of values in 
is contained in the set of input values of 
, satisfying the conditions of Sperner’s lemma. It follows that there exists a 
-simplex 
in 
colored with all 
colors. This is a contradiction, because 
is mapped to all of 
, which is not contained in the domain complex 
. 
10.4 Immediate snapshot model and k-connectivity
In this section we show that if 
is a layered immediate snapshot protocol, then 
is 
-connected for every simplex 
.
10.4.1 The nerve lemma
To compute the connectivity of a complex, we would like to break it down into simpler components, compute the connectivity of each of the components, and then “glue” those components back together in a way that permits us to deduce the connectivity of the original complex from the connectivity of the components.
Definition 10.4.1
Assume that 
is a simplicial complex and 
is a family of non-empty subcomplexes covering 
, i.e., 
. The cover’s nerve complex 
is the abstract simplicial complex whose vertices are the components 
and whose simplices are sets of components 
, of which the intersection 
is non-empty.
Informally, the nerve of a cover describes how the elements of the cover “fit together” to form the original complex. Like the nerve graph, the nerve complex is determined by the cover, not the complex. The next lemma is a generalization of Lemma 10.2.6.
Lemma 10.4.2
Nerve Lemma
Let 
be a cover for a simplicial complex 
, and let 
be some fixed integer. For any index set 
, define 
. Assume that 
is either 
-connected or empty, for all 
. Then 
is 
-connected if and only if the nerve complex 
is 
-connected.
The following special case of the nerve lemma is often useful:
Corollary 10.4.3
If 
and 
are 
-connected simplicial complexes, such that 
is 
-connected, then the simplicial complex 
is also 
-connected.
10.4.2 Reachable complexes and critical configurations
To compute higher-dimensional connectivity, we need to generalize Proposition 10.2.9 to multiple sets.
Lemma 10.4.4
Let 
be sets of process names indexed so that 
.
where 
, the set of processes that take no further steps, satisfies
Proof
We argue by induction on 
. For the base case, when 
is 
, the claim follows from Proposition 10.2.9.
For the induction step, assume the claim for 
sets. Because the 
are indexed so that 
, we can apply the induction hypothesis
where
Since no process in 
takes a step in the intersection,
Applying Proposition 10.2.9 and Equation (10.2.1) yields
We now compute 
, the combined set of processes to halt. First, suppose that 
. It follows that 
, and 
, so 
.
Suppose instead that 
. If 
, then 
, and 
. If 
, then 
, so 
, and 
. Substituting 
yields
where 
, the set of processes that take no further steps, satisfies
For each configuration 
, the reachable complexes 
cover 
. They define a nerve complex 
. The vertices of this complex are the reachable complexes 
, and the 
-simplices are the sets 
such that
We know from Lemma 10.4.4 that
where 
, the set of processes that halt, depends on 
and 
. This complex is non-empty if and only if 
.
Lemma 10.4.5
If 
but each 
, then 
.
, so by 
Lemma 10.4.6
The nerve complex 
is 
-connected.
Proof
We show that the nerve complex is a cone with an apex 
; in other words, if 
is an non-empty simplex in the nerve complex, so is 
. Let 
.
If 
for some 
in 
, there is nothing to prove. Otherwise, assume 
, for 
. The simplex 
is non-empty if
Applying Lemma 10.4.4,
Because each 
, and 
is non-empty, Lemma 10.4.5 implies that 
, so the simplex 
is non-empty.
It follows that every facet of the nerve complex contains the vertex 
, so the nerve complex is a cone, which is 
-connected because it is contractible (see Section 3.5.3).
Theorem 10.4.7
For every wait-free layered immediate snapshot protocol and every input simplex 
, the complex 
is 
-connected.
Proof
We argue by induction on 
. For the base case, when 
, the complex 
is a single vertex, which is trivially 
-connected.
For the induction step, assume the claim for 
processes. Consider 
, where 
. Being 
-connected is an eventual property, so it has a critical configuration 
such that 
is not 
-connected, but 
is 
-connected for every configuration reachable from 
. In particular, for each set of process names 
, each 
is 
-connected. Moreover, the 
cover 
.
Lemma 10.4.4 states that
for 
. Because 
, this complex is the wait-free protocol complex for 
processes, which is either empty or 
-connected by the induction hypothesis.
Lemma 10.4.6 states that the nerve complex is 
-connected, hence 
-connected.
It follows from the nerve lemma that 
was already 
-connected, contradicting the assumption that 
was a critical configuration for 
-connectivity. 
10.5 Chapter notes
Fischer, Lynch, and Paterson [55] were the first to prove that consensus is impossible in a message-passing system where a single thread can halt. They introduced the critical configuration style of impossibility argument. Loui and Abu-Amara [110] and Herlihy [78] extended this result to shared memory. Biran, Moran, and Zaks [18] were the first to draw the connection between path connectivity and consensus.
Chaudhuri [37] was the first to study the 
-set agreement task. The connection between connectivity and 
-set agreement appears in Chaudhuri, Herlihy, Lynch, and Tuttle [39], Saks and Zaharoglou [135], Borowsky and Gafni [23], and Herlihy and Shavit [91].
The critical configuration style of argument to show that a protocol complex is highly connected was used by Herlihy and Shavit [91] in the read-write wait-free model. This style of argument is useful to prove connectivity in models where other communication objects are available in addition to read-write objects, as in Herlihy [78] for path connectivity or Herlihy and Rajsbaum [79] for 
-connectivity. The layered style of argument was used in Chapter 9 to prove connectivity invariants on the sets of configurations after some number of steps of a protocol. It is further explored in Chapter 13. Yet another approach to prove connectivity is in Chapter 7, based on distributed simulations.
As we have seen in this chapter, 
-connectivity is sufficient to prove the 
-set agreement impossibility result. However, it is not a necessary property. In Chapter 9 we saw that the weaker property of being a manifold protocol is also sufficient. Theorem 5.1 in Herlihy and Rajsbaum [82] is a model-independent condition that implies set agreement impossibility in the style of Theorem 10.3.1. The condition is based on homology groups instead of homotopy groups (as is 
-connectivity) and is more combinatorial. In fact, from the manifold protocol property it is quite straightforward to derive the homology condition, as explained by Attiya and Rajsbaum [16].
One of the main ideas in this book is that the power of a distributed computing model is closely related to the connectivity of protocol complexes in the model. For instance, given Theorem 10.3.1, the problem of telling whether set agreement is solvable in a particular model is reduced to the problem of showing that protocol complexes in that model are highly connected. A number of tools exist to show that a space is highly connected, such as subdivisions, homology, the nerve theorem, and others. Matousek [113] describes some of them and discusses their relationship. We refer the interested reader to Kozlov [100, section 15.4] for further information on the nerve lemma; in particular, see [100, Theorem 15.24].
Mostefaoui, Rajsbaum, and Raynal [122] introduced the study of the “condition-based approach” with the aim of characterizing the input complexes for which it is possible to solve consensus in an asynchronous system despite the occurrence of up to 
process crashes. It was further developed, e.g., for synchronous systems, in Mostefaoui, Rajsbaum, Raynal, and Travers [123] and set agreement in [121].
Obstructions to wait-free solvability of arbitrary tasks based on homology theory were studied by Havlicek [76]. This result is further discussed in Havlicek [75], where it is proved that the wait-free full-information protocol complex (using atomic snapshot memory) is homotopy equivalent to the underlying input complex. The derivation of the homotopy equivalence is based on Theorem 10.4.7 (proved originally in [91]).
10.6 Exercises
Exercise 10.1
Prove the following stronger version of Lemma 10.2.6: If each 
is path-connected, then 
is path-connected if and only if the nerve graph 
is path-connected.
Exercise 10.2
Defend or refute the claim that “without loss of generality,” it is enough to prove that 
-set agreement is impossible when inputs are taken only from a set of size 
.
Exercise 10.3
Use the nerve lemma to prove that if 
and 
are 
-connected, and 
is 
-connected, then 
is 
-connected.
Exercise 10.5
Let the simplicial map 
to be a simplicial approximation to the continuous map 
. Show that the continuous map 
is homotopic to 
.
Exercise 10.6
We have defined a simplicial map 
to be a simplicial approximation to the continuous map 
if, for every simplex 
,
An alternative definition is to require that for every vertex 
,
Show that these definitions are equivalent.
Exercise 10.7
Let 
be a configuration, and define
the complex of final configurations reachable by executions in which exactly one process participates in the next layer after 
. Clearly, 
.
Show that 
.
Show that the nerve complex 
is isomorphic to 
, the 
-skeleton of 
.