Classifying Loop Agreement Tasks
Abstract
Recall from Chapter 5, Section 5.6.2 that (colorless) loop agreement is a family of tasks for which the existence of a wait-free read-write protocol is undecidable. Here we give a complete classification of loop agreement tasks. Each loop agreement task can be assigned an algebraic signature consisting of a group 
and a distinguished element 
in 
. Remarkably, this signature completely characterizes the task’s computational power. If 
and 
are loop agreement tasks with respective signatures 
and 
, then 
implements 
if and only if there exists a group homomorphism 
carrying 
to 
. In short, the algorithmic problem of determining how to implement one loop agreement task in terms of another reduces to a problem in group theory.
Keywords
Algebraic signature; Finitely generated groups; Finite group presentation; Fundamental group; Loop agreement; Torsion
A task 
implements task 
if one can construct a wait-free protocol for 
by calling any protocol for 
, possibly followed by access to a shared read-write or snapshot memory. This notion of implementation induces a partial order on tasks and allows us to classify tasks by partitioning them into disjoint classes such that tasks in the same class implement one another. In this sense, the tasks in the same class are computationally equivalent. One class is more powerful than another if any task in the first class implements any class in the second, but not vice versa.
Recall from Section 5.6.2 that loop agreement is a family of colorless tasks for which the existence of a wait-free read-write protocol is undecidable. Here we give a complete classification of loop agreement tasks. Each loop agreement task can be assigned an algebraic signature consisting of a group 
and a distinguished element 
in 
. Remarkably, this signature completely characterizes the task’s computational power. If 
and 
are loop agreement tasks with respective signatures 
and 
, then 
implements 
if and only if there exists a group homomorphism 
carrying 
to 
. In short, the algorithmic problem of determining how to implement one loop agreement task in terms of another reduces to a problem in group theory.
We will see that the loop agreement task corresponding to 
-process, 
-set agreement belongs to the most powerful class in the classification (the maximal element in the classification order), whereas (various forms of) approximate agreement belong to the weakest class (the minimal element). In between is an infinite number of inequivalent classes.
The material in this chapter assumes that the reader has some familiarity with elementary abstract algebra, including finitely generated groups, group homomorphisms, and presentations of finite groups.
15.1 The fundamental group
15.1.1 Basic definitions
Let 
be a 
-dimensional simplicial complex, and let 
be the unit interval 
. Recall from Section 5.6.1 that a path in a complex 
is a continuous map 
. If 
, the path is a loop with base point 
. Two loops with the same base point are homotopic if one can be continuously deformed to the other while leaving the base point fixed. A loop 
is simple if its restriction to 
is injective.
Two paths 
and 
can be concatenated to form another path 
if 
:
In particular, loops with the same base point can be concatenated in two different ways.
The fundamental group 
of 
is defined as follows: The elements of the group are equivalence classes under homotopy of loops with base point 
. The group operation “
” on these equivalence classes is concatenation of their representatives, i.e., 
. It is a standard exercise to check that this operation defines a group whose identity element is the equivalence class 
of the constant loop 
and where the inverse of 
is obtained by traversing 
in the opposite direction,
and 
. The identity element is the equivalence class of contractible loops, those that can be continuously deformed to 
.
For example, the fundamental group of the circle is isomorphic to the group of integers under addition; this group is also called the infinite cyclic group. The constant loop corresponds to the identity element 0; concatenating the constant loop to any other loop does not change its homotopy type. By convention, the loop that wraps around the circle once in the clockwise direction corresponds to the generator 1, and counter-clockwise corresponds to the generator 
. Any loop is homotopic to one that “wraps” around the circle 
times, where positive 
is clockwise and negative 
is counter-clockwise. Furthermore, any two loops that wrap around the circle a different number of times are not homotopic.
If the complex 
is path-connected, its fundamental group is independent of the base point, up to isomorphism. For simplicial complexes, the notions of connected and path-connected coincide, and all the complexes we consider are connected, so we often write 
in place of 
.
Now let 
be another connected simplicial complex, let 
be a continuous map, and let 
be a loop in 
. The composition 
is a loop in 
. Define the map induced by 
to be 
. It is a standard fact that 
is a group homomorphism.
Recall that an edge loop is a loop whose base point is a vertex of 
and whose path is a sequence of oriented edges in 
. Since in a simplicial complex every loop with a base at a vertex is homotopic to a standard loop associated with an edge loop, every element of the fundamental group based at a vertex has a representative that is associated with an edge loop.
15.1.2 A representation of the fundamental group associated with a spanning tree
Assume that 
is a finite connected 
-dimensional simplicial complex. Let 
be a rooted spanning tree of 
. There is a standard representation of the fundamental group 
in terms of generators and relations, which we now proceed to describe. Let 
denote the root of 
, and let 
denote all the vertices of 
.
• Generators of 
. For each 
such that 
is an edge of 
that does not belong to 
, we take a generator 
. For convenience, for all pairs 
such that 
is an edge of 
, we shall set by convention 
. We shall also set 
for all 
, and 
for all 
.
• Relations of 
. Whenever the vertices 
form a 
-simplex of 
, we have a relation
(15.1.1)
Note the following special cases of the relation (15.1.1). If 
and 
are edges of 
, then automatically 
. If 
is an edge of 
and 
is arbitrary, then 
.
To see that the group defined by these generators and relations is isomorphic to the fundamental group 
, simply send each generator 
to the standard loop associated with the edge loop constructed by concatenating the following three paths:
to 
along the tree
to 
along the treeIn particular, we see that the fundamental group of a finite complex is finitely generated.
An alternative way to think of this representation is as follows: Consider the space 
obtained from 
by shrinking the tree 
to a point. This new space has one vertex; all the edges are now loops and all the triangles are now 
-cells, which may have one, two, or three boundary edges. The space 
is topologically the same as 
; speaking formally, it is homotopy equivalent to 
. In particular, the fundamental groups are the same. The above representation can now be viewed as the representation of the fundamental group of 
, with edges of 
giving generators and 
-cells giving relations. As mentioned, there are then three different kinds of relations. The 
-cell, having only one boundary edge, gives relation 
. The 
-cell with two boundary edges will give a relation 
or 
. Finally, the 
-cell with three boundary edges will give a relation of the type (15.1.1).
15.2 Algebraic signatures
Let 
again be a 
-dimensional connected simplicial complex, and consider a loop agreement task 
. The triangle loop 
represents an element 
of the fundamental group 
.
Definition 15.2.1
We call the pair (
the algebraic signature of the loop agreement task 
.
Let 
be another 
-dimensional connected simplicial complex, and consider a loop agreement task 
, where 
is some triangle loop. We use the notation
to denote any group homomorphism 
from 
to 
that maps 
to 
, where, on the left side, 
is taken to be the base point and, on the right side, 
is taken to be the base point.
Fact 15.2.2
Assume that 
and 
are two distinct points of a topological space 
, and assume that 
are two simple paths from 
to 
such that 
. Then the paths 
and 
are homotopic.
Furthermore,
denotes a continuous map from 
to 
such that 
and 
for all 
. Let 
denote the homomorphism on underlying fundamental groups induced by 
.
Lemma 15.2.3
If 
is a continuous map as stated, then 
.
Proof
We can use Fact 15.2.2 to reparameterize 
and obtain a loop 
such that 
. This of course means 
. Since 
and 
are homotopic, we conclude that 
. 
We can show that the converse also holds. To start with, we have the following general result.
Lemma 15.2.4
Assume that 
and 
are finite simplicial complexes, the complex 
is 
-dimensional, 
is a vertex of 
, and 
is a vertex of 
. Assume 
is a group homomorphism. Then there exists, a continuous map 
such that 
and 
.
Proof
Let 
be a spanning tree of 
, rooted at 
. Set as before 
, which is the space obtained from 
by shrinking 
to a point, which we call 
. Let 
denote the quotient map, which takes 
to 
. Since 
is a tree, 
is an isomorphism, which we use to identify these two groups.
We now proceed to define a continuous map 
. First we set 
. Next, take any directed edge 
of 
. Identify it with a characteristic loop 
. It corresponds to an element 
. Let 
be a representative loop of 
, 
. Define 
for all 
. This defines a continuous function 
on the 
-skeleton of 
.
As a last step, we can extend 
to the rest of 
, going cell by cell. For each 
-cell 
can be extended to 
if and only if its boundary loop is contractible in 
. Clearly, the boundary loop of 
represents the trivial element of the fundamental group 
. Since the map 
is a group homomorphism, the image of the boundary map under 
represents the trivial element of 
. Thus 
can be extended to 
, and since this can be done for every 
-cell, we are done.
Finally, we construct the continuous map 
as a composition of 
and 
. 
We now apply this result to the special situation of triangle loops.
Lemma 15.2.5
Assume 
and 
are 
-dimensional connected simplicial complexes, 
is a triangle loop in 
, and 
is a triangle loop in 
. If there exists a group homomorphism 
, then there exists a continuous map 
.
Proof
By Lemma 15.2.4, there exists a continuous map 
, which takes 
to 
. This means that 
takes the loop 
to a loop 
, which is homotopic to 
. Let 
be the loop homotopy from 
to 
. It is a standard topological fact, which we use here without proof, that the homotopy 
can be extended to deform the whole map 
to a map 
. This map 
is continuous and takes 
to 
.
We finish the proof by remarking that the claim that 
can be extended to all of 
follows from the fact that 
is a cofibration (see the chapter notes). 
Combining Lemmas 15.2.3 and 15.2.5 yields
Theorem 15.2.6
There exists a continuous map 
if and only if there exists a homomorphism 
.
15.3 Main theorem
In this section, we demonstrate the equivalence of the existence of a continuous map 
and the existence of an implementation of 
by an instance of 
. This will imply our main result, Theorem 15.3.8.
15.3.1 Map implies protocol
Recall that a simplicial map 
is a simplicial approximation of a continuous map 
if, for every point 
in 
lies in the carrier of 
. The Simplicial Approximation Theorem 3.7.5 guarantees that every such 
has a simplicial approximation 
for large enough 
.
Lemma 15.3.1
Let 
and 
be simplicial complexes with respective simplicial subcomplexes 
and 
, and let 
be a continuous map such that 
. If 
is a simplicial approximation to 
, then 
.
Proof
Let 
be a point of 
. The carrier of 
is in 
, since 
. Because 
is a simplicial approximation to 
. 
In the barycentric agreement task, processes start with vertices in a simplex 
in a complex 
(of arbitrary dimension), and they must converge to vertices of a simplex in 
, the 
-th barycentric subdivision of the input simplex.
We can now settle one direction of our main theorem.
Lemma 15.3.2
If there exists a continuous map 
, then an instance of 
implements 
.
Proof
By the Simplicial Approximation Theorem, 
has a simplicial approximation
for some 
. Assume that we have 
and that 
. Assume that a process has input 
. We proceed as follows.
• Let this process run the wait-free protocol for 
with input 
, and let 
be its output.
• Run the wait-free read-write 
-th barycentric agreement protocol for 
with 
as input, and let 
be its output.
and halt.The entire protocol is wait-free because all its parts are wait-free.
The outputs of the 
protocol lie on a single simplex of 
, and the outputs of the 
-th barycentric agreement protocol lie on a single simplex of 
. Because 
is a simplicial map, the decision values lie on a single simplex of 
.
Suppose the processes have two distinct inputs 
and 
(where we identify 
with 
). The outputs of the 
protocol lie on a single simplex of 
, and the outputs of the 
-th barycentric agreement protocol, lie on a single simplex of 
. Because 
and 
are edge loops, 
and 
can be considered subcomplexes of 
and 
respectively. Because 
, Lemma 15.3.1 states that the simplicial approximation 
carries 
to 
. All processes thus choose vertices in a simplex of 
.
Suppose all processes have the same input 
. The outputs of the 
protocol are all 
, and the outputs of the 
-th barycentric agreement protocol are all 
. Since 
carries 
to 
, all processes thus choose 
. 
15.3.2 Protocol implies map
We now turn our attention to the other direction: If a protocol exists by which an instance of 
implements 
, then so does a continuous map 
. Assume that we have 
and that 
. Our basic strategy is the following: We may assume without loss of generality that the protocol has two phases. In the first phase, it calls a “subroutine” to solve 
, and in the second phase, it uses the result as input to a pure read-write phase. We can treat the read-write phase as a protocol in its own right, where each process has a vertex of 
as input and chooses a vertex of 
as output.
Formally, there is a simple way to transform 
into an output complex.
Definition 15.3.3
Let 
be a complex. The colorized complex 
is defined as follows:
• The vertices of 
are all combinations of the form 
, where 
is a process name and 
a vertex of 
.
• Vertices 
span an 
-simplex in 
if and only if the 
are distinct, and 
(not necessarily distinct) span a simplex in 
.
Let 
be the projection simplicial map that discards colors.
The read-write phase can now be recast as the decision task 
, where 
is the “colorized” version of the loop agreement relation. Let 
denote the maximal simplex of 
such that 
. Let 
be the subcomplex of 
such that, for all 
, and similarly for 
and 
. The relation 
carries each 
to 
and each simplex of 
to 
.
The circumstances under which a decision task has a wait-free read-write implementation are given by the following asynchronous computability theorem:
Theorem 15.3.4
A decision task 
has a wait-free protocol using read-write memory if and only if there exists a chromatic subdivision 
of 
and a color-preserving simplicial map
such that, for each vertex 
in 
, 
.
Applying this theorem to the read-write phase yields a color-preserving simplicial map
that carries each 
to 
and carries each 
to 
.
Composing 
with the color-discarding projection map 
yields a simplicial map
The map 
carries each 
to 
and carries each 
to 
.
We now claim that we can assume without loss of generality that 
has a 
-coloring.
Lemma 15.3.5
If 
is a 
-dimensional complex, then 
has a 
-coloring.
Proof
Assign each 
in 
the label 
. The result is a 
-coloring. 
Lemma 15.3.6
The tasks 
and 
are equivalent; an instance of one implements the other.
Proof
To implement 
, each process runs the protocol for 
and feeds the output to a round of barycentric agreement.
To implement 
, each process runs the protocol for 
, yielding output 
. Each process then chooses any vertex in 
. 
Assume that 
is 
-colorable. Pick a 
-coloring for 
with the first three process names, and let 
be the resulting colored complex. Clearly, 
and 
are isomorphic (the only difference is the labeling of vertices). Let 
and 
denote the images of 
and 
in 
.
Note that 
is a subcomplex of 
, so 
is a subcomplex of 
. We now have a simplicial map
the restriction of 
. Thus, the map 
carries each 
to 
, and each 
to 
.
Lemma 15.3.7
If an instance of 
implements 
, then there exists a continuous map 
.
Proof
The map 
constructed above induces a continuous map
carrying each 
to 
and each 
to 
. Since 
is the desired continuous map 
carrying each 
to 
and each 
to 
. 
Theorem 15.3.8
An instance of 
implements 
if and only if there exists a group homomorphism 
.
Proof
From Lemmas 15.3.2, 15.3.7, and Theorem 15.3.8. 
15.4 Applications
We start with a known result, but one that illustrates the power of the theorem.
Proof
Recall that (3,2)-set agreement can be viewed as 
, where 
is the triangle loop 
. It is a standard result that 
is infinite cyclic with generator 
. Implementing 
-set agreement wait-free is the same as implementing it with 
-th barycentric agreement 
. Because 
is trivial, the only homomorphism 
is the trivial one. It carries 
to the identity element of the group and not to 
. 
It is now easy to identify the most powerful and least powerful loop agreement tasks. We say that a task is universal if it implements any loop agreement task whatsoever.
Proof
As was just mentioned, (3,2)-set agreement is 
, where 
is as above. It is a standard result that 
is the infinite cyclic group 
with generator 
. To implement any 
, let 
. 
Proof
The complex for uncolored simplex agreement has a trivial fundamental group because it is a subdivided simplex, and hence its polyhedron is a convex subset of Euclidean space. To implement this task with any 
, let 
of every element be the identity. 
As another example that illustrates the power of the theorem, we show that the loop agreement tasks classification is undecidable. In fact, we prove a more specific result: It is undecidable to compute if a loop agreement task belongs to the weakest class (of loop agreement tasks that are equivalent to uncolored simplex agreement, by the previous proposition).
The following gives a different proof of the result that wait-free task solvability is undecidable.
Proposition 15.4.4
It is undecidable whether an instance of uncolored simplex agreement implements 
.
Proof
By Theorem 15.3.8, an instance of uncolored simplex agreement 
implements 
if and only if there exists a group homomorphism 
. Since 
is the trivial group, 
exists if and only if 
is the identity of 
, that is, if and only if 
is contractible in 
. But it is a classic result that loop contractibility is undecidable in 
-dimensional complexes. 
15.5 Torsion classes
The torsion number of 
is the least positive integer 
such that 
is the identity element of 
; in group theory this is called the order of the element 
of 
. If no such 
exists, then the order is infinite. Every loop agreement task has a well-defined torsion number. Define torsion class 
to be the tasks with torsion number 
.
As an example of a loop agreement task with a nontrivial (i.e., not 
and not 
) torsion number, let 
be complex whose polyhedron is isomorphic to a Moebius strip, and choose a triangle loop 
that geometrically corresponds to the “equator” of the strip. Then 
is the generator of 
and has torsion class 
.
How much information does a task’s torsion number convey? The following properties follow directly from Theorem 15.3.8:
• If a task in class 
(finite) implements a task in class 
, then 
(
divides 
).
• Each torsion class includes a universal task that solves any loop agreement task in that class.
• A universal task for class 
(finite) is also universal for any class 
where 
.
• A universal task for class 
(finite) does not implement any task in class 
if 
does not divide 
.
is universal for any class 
.Torsion classes form a coarser partitioning than our complete classification, but they are defined in terms of simpler algebraic properties, and they too have an interesting combinatorial structure.
15.6 Conclusions
We have established a connection between the computational power of a class of distributed tasks and the structure of the fundamental groups of topological spaces related to the tasks. This connection raises a number of open problems. Can we use a similar approach to characterize the computational power of tasks other than loop agreement tasks? A potential obstacle here is that Theorem 15.3.8 is known to be false above dimension two, so it may be necessary to settle for weaker characterizations in higher dimensions. Can we characterize the computational power of compositions of tasks? In the implementations considered here, we compose one copy of a protocol for 
with an arbitrary read-write protocol to construct a protocol for 
. Can we give a similar characterization for multiple tasks in terms of the fundamental groups of their components? There is a need for further investigation into these questions.
15.7 Chapter notes
Most of the results in this chapter originally appeared in Herlihy and Rajsbaum [83].
The notion of loop agreement task was extended to degenerate loop agreement tasks by Liu et al. [108,109], A degenerate loop agreement task is defined by a graph (1-complex) 
with two distinguished vertices, 
and 
. Each process starts with a binary input (0 or 1). Each process halts with a vertex from 
. If the inputs of all participating processes are 0, the processes halt with output value 
, and if all values are 1, they halt with 
. If the inputs are mixed, each process processes halts with a vertex from 
, and all vertices chosen must lie on an edge or vertex (0- or 1-simplex) of 
. The degenerate loop agreement tasks fall into two equivalence classes: those that are equivalent to consensus and those that are equivalent to read-write memory. The “consensus” class is universal in the sense that any task in that class implements any degenerate loop agreement task. The “read-write” class is the weakest class in the sense that any degenerate loop agreement task implements any task from the read-write class.
Fraignaud, Rajsbaum, and Travers [59] use techniques similar to the ones in this chapter to obtain a classification of locality-preserving tasks in terms of their computational power, considering a relationship with covering spaces (the classic algebraic topology notion).
More on cofibrations can be found in Kozlov [100, Chapter 7]. The representation of the fundamental group of a simplicial complex from subSection 15.1.2 is taken from Armstrong [7, p. 135]. Notions related to the torsion number appear in Munkres [124, p. 22] and in Armstrong [7, p. 178].
15.8 Exercises
Exercise 15.1
Find a loop agreement task 
that is equivalent to the 
-set agreement but such that the fundamental group of 
is not 
.
Exercise 15.2
Consider the loop agreement task 
, where we no longer assume that 
is 
-dimensional. What can be said about the solvability of 
?
Exercise 15.3
Construct an infinite sequence of loop agreement tasks 
, such that for all 
the task 
is implemented by the task 
, but not vice versa.