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

1. Basic idea

• Represent IndistinguishabilityProofs using tools from topology.

• Typical indistinguishability proof:
  • Show certain executions are indistinguishable to some process (and thus that process produces same output in both executions).

  • In general case, have a chain of schedules S₁, S₂...,S_k such that for each i there is some p with S_i|p = S_i+1|p. The restriction to p acts as an edge between points representing executions, and we use the existence of a path of such edges as a proof that the decision value in S₁ is the same as in S_k, assuming all processes must agree on the decision value.

• Topological version:
  • Essentially the dual of the above: points are now individual process states (or histories), and edges (and higher-dimensional structures) represent consistent states of different processes (i.e., executions in which both states occur).

  • Considering many possible states produces a simplicial complex, a finite combinatorial structure used in topology to model continuous surfaces.

  • Properties of the simplicial complex resulting from some protocol or problem specification can then be used to determine properties of the underlying protocol or problem.
  • Topologists know a lot of properties to look at.

2. Representing distributed computing using topology

Topology is the study of properties of shapes that are preserved by continous functions between their points that have continuous inverses, which get the rather fancy name of homeomorphisms. A continuous function¹ is one that maps nearby points to nearby points. A homeomorphism is continuous in both directions: this basically means that you can stretch and twist and otherwise deform your object however you like, as long as you don't tear it (which would map nearby points on opposite sides of the tear to distant points) or glue bits of it together (which turns into tearing when we look at the inverse function). Topologists are particularly interested in showing when there is no homeomorphism between two objects; the classic example is that you can't turn a sphere into a donut without damaging it, but you can turn a donut into a coffee mug (with a handle).

Working with arbitrary objects embedded in umpteen-dimensional spaces is messy, so topologists invented a finite way of describing certain well-behaved objects combinatorially, by replacing ugly continuous objects like sphere and coffee mugs with simpler objects pasted together in complex ways. The simpler objects are simplexes, and the complex pasted-together objects are called simplicial complexes. The nifty thing about simplical complexes is that they give a convenient tool for describing what states or outputs of processes in a distributed algorithm are "compatible" in some sense, and because topologists know a lot about simplicial complexes, we can steal their tools to describe distributed algorithms.

2.1. Simplicial complexes and process states

The formal definition of a k-dimensional simplex is the convex closure of (k+1) points { x₁...x_k+1 } in general position; the convex closure part means the set of all points ∑ a_ix_i where ∑ a_i = 1 and each a_i ≥ 0, and the general position part means that the x_i are not all contained in some subspace of dimension (k-1) or smaller (so that the simplex isn't squashed flat somehow). What this gives us is a body with (k+1) corners and (k+1) faces, each of which is a (k-1)-dimensional simplex (the base case is that a 0-dimensional simplex is a point). Each face includes all but one of the corners, and each corner is on all but one of the faces. So we have:

• 0-dimensional simplex: point.
• 1-dimensional simplex: line segment with 2 endpoints (which are both corners and faces).
• 2-dimensional simplex: triangle (3 corners with 3 1-dimensional simplexes for sides).

• 3-dimensional simplex: tetrahedron (4 corners, 4 triangular faces).

• 4-dimensional simplex: 5 corners, 5 tetrahedral faces. It's probably best not to try to visualize this.

A simplicial complex is a bunch of simplexes stuck together; formally, this means that we pretend that some of the corners (and any faces that include them) of different simplexes are identical points. Combinatorially, an (abstract) simplicial complex is just a collection of sets with the property that if A is a subset of B, and B is in the complex, then A is also in the complex (this means that if some simplex is included, so are all of its faces, their faces, etc.). This combinatorial version is nice for reasoning about simplicial complexes, but is not so good for drawing pictures. In order to turn an abstract simplicial complex into a

The trick to using this for distributed computing problems is that we are going to build simplicial complexes by letting points be process states (or sometimes process inputs or outputs), each labeled with a process id, and letting the sets that appear in the complex be those collections of states/inputs/outputs that are compatible with each other in some sense. For states, this means that they all appear in some global configuration in some admissible execution of some system; for inputs and outputs, this means that they are permitted combinations of inputs or outputs in the specification of some problem.

Example: For 2-process binary consensus with processes 0 and 1, the input complex, which describes all possible combinations of inputs, consists of the sets { {}, {p0}, {q0}, {p1}, {q1}, {p0,q0}, {p0,q1}, {p1,q0}, {p1,q1} }, which we might draw in glorious ASCII art like this:

p0-q0
 | |
q1-p1

Note that there are no edges from p0 to p1 or q0 to q1: we can't have two different states of the same process in the same global configuration.

The output complex, which describes the permitted outputs, is { {}, {p0}, {q0}, {p1}, {q1}, {p0,q0}, {p1,q1} }. As a picture, this omits two of the edges (1-dimensional simplexes) from the input complex:

p0-q0
    
q1-p1

One thing to notice about this output complex is that it is not connected: there is no path from the p0-q0 component to the q1-p1 component.

Here is a simplicial complex describing the possible states of two processes p and q, after each writes 1 to its own bit then reads the other process's bit. The number after each process id is 1 if the process saw a 1 and ⊥ if it didn't (here ⊥ means 0, but we want to make it look a little bit less like the previous cases).

p⊥-q1-p1-q⊥

This expresses the constraint that if we both write before we read, then if I don't see your value you must see mine (which is why there is no p0-q0 edge), but all other combinations are possible. Note that this complex is connected: there is a path between any two points.

Here's a fancier version in which each process writes its input (and remembers it), then reads the other process's register (i.e., a one-round full-information protocol). We now have final states of the form <process id><input><value read>, e.g. p1⊥ if p starts with 1 but sees a null and q01 if q starts with 0 but sees p's 1. The general rule is that two states are compatible if p either sees nothing or q's actual input and similarly for q, and that at least one of p or q must see the other's input. This gives the following simplicial complex:

p0⊥-q00-p00-q0⊥
 |           |
q10         p10
 |           |
p01         q01
 |           |
q1⊥-p11-q11-p1⊥

The fact that this looks like four copies of the p⊥-q1-p1-q⊥ complex pasted into each edge of the input complex is not entirely an accident. Again, the resulting complex is connected.

2.2. Simplicial maps and specifications

One thing we can immediately conclude from the fact that the output complex for consensus is not connected but the ones describing our simple protocols are is that we can't solve consensus (non-trivially) using these protocols. The reason is that to solve consensus using either protocol, we would need to have a mapping from states to outputs (this is just whatever rule tells each process what to decide in each state) with the property that if some collection of states are consistent, then the outputs they are mapped to are consistent.

In simplical complex terms, this means that the mapping from states to outputs is a simplicial map, a function f from points in one simplicial complex C to another simplicial complex D such that for any simplex A ∈ C, f(A) = { f(x) | x ∈ A } gives a simplex in D. (Recall that consistent = simplex is included, for both the state complex and the output complex.) A mapping from states to outputs that satisfies the consistency requirements encoded in the output complex s always a simplicial map, with the additional requirement that it preserves process ids (we don't want process p to decide the output for process q). Conversely, any id-preserving simplicial map gives an output function that satisfies the consistency requirements.

Simplicial maps are examples of continuous functions, which have all sorts of nice topological properties. One nice property is that a continuous function can separate a connected space into disconnected components. We can prove this directly for simplical maps: if there is a path of 1-simplexes {x₁,x₂}, {x₂,x₃}, ... {x_k-1,x_k} from x1 to xk in C, and f:C→D is a simplicial map, then there is a path of 1-simplexes {f(x₁),f(x₂)}, ... from f(x₁) to f(x_k). Since being connected just means that there is a path between any two points, if C is connected we've just shown that f(C) is as well.

Getting back to our consensus example, it doesn't matter what simplicial map f you pick to map process states to outputs; since the state complex C is connected, so is f(C), so it lies entirely within one of the two connected components of the output complex. This means in particular that everybody always outputs 0 or 1: the protocol is trivial.

2.3. Subdivisions

In the simple write-then-read protocol above, we saw a single input edge turn into 3 edges. Topologically, this is an example of a subdivision, where we represent a simplex using several new simplexes pasted together that cover exactly the same points.

Certain classes of protocols naturally yield subdivisions of the input complex. A protocol is in normal form if each process alternates between writing out its current state and taking a snapshot of the other process's states. In one dimension (the n=2 case where all global configurations are 1-simplexes), this gives a subdivision at each step matching the p⊥-q1-p1-q⊥ pattern we've already seen. In higher dimensions, we don't get a subdivision exactly; instead we get a structure that has some extra simplexes sticking out of it that can't be tacked down easily. But if we omit these extra simplexes, we can get a subdivision corresponding to a limited set of executions.

A picture of this process in action can be found in Figures 25 and 26 from the Herlihy-Shavit paper.

2.4. Mapping inputs to outputs

For general decision tasks, it's not enough for the outputs to be consistent with each other. They also have to be consistent with the inputs. This can be expressed by a relation Δ between input simplexes and output simplexes.

Formally, a decision task is modeled by a triple (I, O, Δ), where I is the input complex, O is the output complex, and (A,B) ∈ Δ if and only if B is a permissible output given input I. Here there are no particular restrictions on Δ (for example, it doesn't have to be a simplicial map or even a function), but it probably doesn't make sense to look at decision tasks unless there is at least one permitted output simplex for each input simplex.

3. The asynchronous computability theorem

Given a decision task specified in this way, there is a topological characterization of when it has a wait-free solution. This is given by the Asynchronous Computability Theorem (Theorem 3.1 in the paper), which says:

Theorem

A decision task (I,O,Δ) has a wait-free protocol using shared memory if and only if there exists a chromatic subdivision σ of I and a color-preserving simplicial map μ: σ(I) → O such that for each simplex s in σ(I), μ(S) ∈ Δ(carrier(S, I)).

To unpack this slightly, a chromatic subdivision is a subdivision where each vertex is labeled by a process id (a color), and no simplex has two vertices with the same color. A color-preserving simplicial map is a simplicial map that preserves ids. The carrier of a simplex is the subdivision is whatever simplex it is part of. So the theorem says that I can only solve a task if I can find a simplicial map from a subdivision of the input complex to the output complex that doesn't do anything strange to process ids and that is consistent with Δ.

Looking just at the theorem, one might imagine that the proof consists of showing that the protocol complex defined by the state complex after running the protocol to completion is a subdivision of the input complex, followed by the same argument we've seen already about mapping the state complex to the output complex. This is almost right, but it's complicated by two inconvenient facts: (a) the state complex generally isn't a subdivision of the input complex, and (b) if we have a map from an arbitrary subdivision of the input complex, it is not clear that there is a corresponding protocol that produces this particular subdivision.

So instead the proof works like this:

Protocol implies map

Even though we don't get a subdivision with the full protocol, there is a restricted set of executions that does give a subdivision. So if the protocol works on this restricted set of executions, an appropriate map exists.

Map implies protocol

This is trickier; essentially, the proof gives an explicit algorithm for simplex agreement, the problem of getting the processes to agree on a particular simplex contained within the subdivision of their original common input simplex. This is based on a similar protocol by Borowsky and Gafni for solving k-set agreement.

We won't go into the details of either of these.

4. Proving impossibility results

To show something is impossible using the ACT, we need to show that there is no color-preserving simplicial map from a subdivision of I to O satisfying the conditions in Δ. This turns out to be equivalent to showing that there is no continuous function from I to O with the same properties, because any such simplicial map can be turned into a continuous function (on the geometric version of I, which includes the intermediate points in addition to the corners). Fortunately, topologists have many tools for proving non-existence of continuous functions.

4.1. k-connectivity

Define the m-dimensional disk to be the set of all points at most 1 unit away from the origin in ℝ^m, and the m-dimensional sphere to be the surface of the (m+1)-dimensional disk (i.e., all points exactly 1 unit away from the origin in ℝ^m). Note that what we usually think of as a sphere (a solid body), topologists call a disk, leaving the term sphere for just the outside bit.

An object is k-connected if any continuous image of an m-dimensional sphere can be extended to a continuous image of an (m+1)-dimensional disk, for all m ≤ k. This is a roundabout way of saying that if we can draw something that looks like a deformed sphere inside our object, we can always include the inside as well: there are no holes that get in the way. The punch line is that continuous functions preserve k-connectivity: if we map an object with no holes into some other object, the image had better not have any holes either.

Ordinary path-connectivity is the special case when k = 0; here, the 0-sphere consists of 2 points and the 1-disk is the path between them. So 0-connectivity says that for any 2 points, there is a path between them.

For 1-connectivity, if we draw a loop (a path that returns to its origin), we can include the interior of the loop somewhere. One way to thinking about this is to say that we can shrink the loop to a point without leaving the object (the technical term for this is that the path is null-homotopic, where a homotopy is a way to transform one thing continuously into another thing over time and the null path sits on a single point). An object that is 1-connected is also called simply connected.

For 2-connectivity, we can't contract a sphere (or box, or the surface of a 2-simplex, or anything else that looks like a sphere) to a point.

The important thing about k-connectivity is that it is possible to prove that any subdivision of a k-connected simplicial complex is also k-connected (sort of obvious if you think about the pictures, but it can also be proved formally), and that k-connectivity is preserved by simplicial maps (if not, somewhere in the middle of all the k-simplexes representing our surface is a (k+1)-simplex in the domain that maps to a hole in the range, violating the rule that simplicial maps map simplexes to simplexes). So a quick way to show that the Asynchronous Computability Theorem implies that something is not asynchronously computable is to show that the input complex is k-connected and the output complex isn't.

4.2. Impossibility proofs for specific problems

Here are some applications of the Asynchronous Computability Theorem and k-connectivity:

Consensus

There is no nontrivial wait-free consensus protocol for n ≥ 2 processes. Proof: The input complex is 1-connected, but the output complex is not, and we need a map that covers the entire output complex (by nontriviality).

k-set agreement

There is no wait-free k-set agreement for n ≥ k+1 processes. Proof: The output complex for k-set agreement is not k-connected, because buried inside it are lots of (k+1)-dimensional holes corresponding to missing simplexes where all k+1 processes choose different values. But these holes aren't present in the input complex—it's OK if everybody starts with different inputs—and the validity requirements for k-set agreement force us to map the surfaces of these non-holes around holes in the output complex.

Renaming

There is no wait-free renaming protocol with less than 2n-1 output names for all n. The general proof of this requires showing that with fewer names we get holes that are too big (and ultimately reduces to Sperner's Lemma); for the special case of n=3 and m=4, see Figure 9 in the Herlihy-Shavit paper, which shows how the output complex of renaming folds up into the surface of a torus. This means that renaming for n=3 and m=4 is exactly the same as trying to stretch a basketball into an inner tube.

---

CategoryDistributedComputingNotes