$Protocol(U^{{}^{\prime}},V^{{}^{\prime}})$ and $Protocol(U,V)$ since $s^{k}$
is compatible by assumption. The high-level idea of this section is to use
these shared output configurations to connect terminated values from different
protocols and therefore to construct a protocol for $Input(U,V)$.

Before introducing the adversarial strategy to finalize the subcomplex
$Ch^{r_{max}-1}(Input(U,V))$, we will discuss some properties of
$Protocol(U,V)$. Theorem 5.3 tells us that there exists a restricted protocol
$Protocol(U,V)$ if and only if the task $(lk(\tau,\mathcal{I})$,
$\mathcal{O}_{\tau}^{i}\backslash\tau$, $\Delta_{\tau})$ has a protocol for
some $\mathcal{O}_{\tau}^{i}$, where $\Delta_{\tau}$ carries a simplex
$\tau^{{}^{\prime}}$ $\subseteq$ $lk(\tau,\mathcal{I})$ to the complex
$\Delta(\tau^{{}^{\prime}}*\tau)\backslash\tau$. We can construct a standard
form of $Protocol(U,V)$ in which the processes in $U$ decide the label values
of $\mathcal{O}_{\tau}^{i}$, and the processes in $\Pi-U$ execute the protocol
for task $(lk(\tau,\mathcal{I})$, $\mathcal{O}_{\tau}^{i}\backslash\tau$,
$\Delta_{\tau})$. An important property of a protocol of this form is that
every output $n$-simplex will share the vertices corresponding to the
processes in $U$. However, we cannot replace $Protocol(U,V)$ with its standard
form, since the output value of the solo execution of each vertex of
$Input(U,V)$ can be changed. For example, in Figure 1 when protocol
$Protocol(\\{p_{0},p_{2}\\},\\{v_{0},v_{2}\\})$ is replaced by its standard
form, the output value corresponding to schedule $v_{0},v_{2},v_{2},...$
changes. Therefore, we have to discuss the most general protocol for each
$Input(U,V)$ that may not be in standard form.

For each n-clique $s^{n}$ in $Ch^{r_{max}-1}(C)$ where $C\in Input(U,V)$, we
can divide the terminated configurations in $S^{t}(s^{n})$ into disjoint sets
such that the terminated configurations in each set will have the same label
and the active distances between them are 0. By invariant(3), this division
into sets is always possible. In $S^{t}(s^{n})$ where $s^{n}$ has an
intersection with some $Input(U^{{}^{\prime}},V^{{}^{\prime}})$, some sets may
have the label $(U^{{}^{\prime}},V^{{}^{\prime}})$. In the proof of Lemma
5.10, the terminated configurations of an opposite label will be limited to
some geometric distance(not the distance measured by the number of vertex)
from the intersection subsimplex. In other words, a terminated set of some
opposite label will be distant from $S^{t}(s^{ni})$, where $s^{ni}$ is the
subsimplex of $s^{n}$ consisting of non-intersection vertices of $s^{n}$.

The adversary progresses in four stages. In some stages, the adversary will
terminate the vertices adjacent to an existing terminated set. We will say
that the adversary adds a new layer to this set. The goal is to add enough
layers to those terminated sets with some opposite clique such that the output
configurations of the outermost layer will be the protocol configuration of
$s^{n}$. After this, the undefined vertices in $S^{t}(s^{n})$ will be
terminated with the protocol configuration of $s^{n}$.

In the first stage, the adversary will subdivide $S^{t}$ and increment $t$
many times so that the layers added in later stages do not overlap and will
still be distant from $S^{t}(s^{ni})$. This is possible since the adversary
can know the upper bound of the added layers in advance, as shown in the
following discussion.

In the second stage, the adversary will terminate the vertices adjacent to a
terminated vertex $v$ with the label of $v$. The choice of label will be
unique according to Invariant(3). Note that we do not use rule (2) which may
increase the number of vertices to terminate and therefore lead to an infinite
sequence. Those results assuming the usage of rule (2) will still be valid
since the adversary will subdivide enough times in the first stage. The
reasons to introduce this stage will be formulated in later discussions of
finalization, and even those discussions of assignment queries.

Until now, we have not imposed any requirements on task setting. Stage 3
relies on the condition that the task is colorless as defined in Section 3.
Let $s^{n}$ be some n-clique in $Ch^{r_{max}}(\sigma)$ where $\sigma$
represents an initial configuration. We want such a property: if an output
configuration is valid for some subsimplex $s^{k}$ of $s^{n}$ and other
vertices of $s^{n}$ have an equal or larger carrier than $carrier(s^{k})$,
then other processes can use the values of $s^{k}$ as their output values.
This property is intrinsic when the general task
$(\mathcal{I},\mathcal{O},\Delta)$ is colorless. Perhaps, we need to explain
why this property is needed. Recall that each intersection simplex in
$Ch(\mathcal{I})$ is compatible. A shared output configuration $s^{k}$ reached
from an intersection simplex will have a dimension less than $n$. This
property allows the adversary to obtain a valid $n$-dimensional output
configuration for $s^{n}$. The readers can imagine

Then we will discuss the adversarial strategy in the third stage. For each
label $(U,V)$ and some opposite label $(U^{{}^{\prime}},V^{{}^{\prime}})$,
there is a complex $C_{in}$ consisting of all the intersection simplices in
$Ch^{1}(C)$. For example, when $U_{1}\nsubseteq U_{2}$, $\Xi(C\uparrow
U_{1})\bigcap\Xi(C\uparrow U_{2})$ equals $(\Xi\downarrow U_{1}\bigcup
U_{2})(C\uparrow U_{1}\bigcup U_{2})$, which is the standard chromatic
subdivision of a ($|\Pi|-|U_{1}\bigcup U_{2}|$)-simplex. Recall that a facet
of a complex is a simplex with maximum dimension. The complex $C_{in}$ is pure
and we will discuss each facet of it.

Let $s^{n}$ be an $n$-clique in $Ch^{r_{max}-1}(Input(U,V))$ that has an
intersection with $Input(U^{{}^{\prime}},V^{{}^{\prime}})$. Then the n-clique
$s^{n}$ can be projected onto a simplex $prj(\sigma)$ in
$Ch^{r_{max}-1}(C_{in})$ which consists of all the intersection vertices of
$s^{n}$. The adversary will process $n$-cliques in
$Ch^{r_{max}-1}(Input(U,V))$ according to their projections, since the task is
colorless.

For each intersection facet $s^{k}$, we can classify all simplices in
$Ch^{r_{max}-1}(s^{k})$ into categories by calculating the smallest carrier in
$Ch^{1}(C)$, as shown by different colors in Figure 2. We define the carrier
of a category as the smallest carrier in $Ch^{1}(C)$. By assumption, the
carrier of a category will be compatible. But before we go into the details,
we will present the definitions of some concepts and prove a lemma that
justifies subsequent adversarial operations.

Figure 2. Categories of 2-simplices in $Ch^{2}(s^{2})$

Categories of 2-simplices in $Ch^{2}(s^{2})$

The first is a topological concept. We will use the definition of (Spa, 66). A
simplicial complex is said to be homogeneously n-dimensional if every simplex
is a face of some n-simplex of the complex. An n-dimensional pseudomanifold is
defined to be a simplicial complex $\mathcal{K}$ such that

  * (a)

$\mathcal{K}$ is homogeneously n-dimensional.

  * (b)

Every $(n-1)$-simplex of $\mathcal{K}$ is the face of at most two n-simplices
of $\mathcal{K}$.

  * (c)

If $s$ and $s^{{}^{\prime}}$ are n-simplices of $\mathcal{K}$, there is a
finite sequence $s=s_{1},s_{2},\cdots,s_{m}=s^{{}^{\prime}}$ of n-simplices of
$\mathcal{K}$ such that $s_{i}$ and $s_{i+1}$ have an $(n-1)$ face in common
for $1\leq i<m$.

There is a relation denoted by $s\sim s^{{}^{\prime}}$ in the set of
n-simplices of a pseudomanifold defined by $s\sim s^{{}^{\prime}}$ if and only
if there exists a finite sequence $s=s_{1},s_{2},\cdots,s_{m}=s^{{}^{\prime}}$
such that $s_{i}$ and $s_{i+1}$ have an $(n-1)$ face in common, as in
condition (c). Obviously, this relation is a reflexive, symmetric, and
transitive relation, and therefore an equivalence relation. An important
property proved in (Spa, 66) is that any subdivision of a pseudomanifold is
also a pseudomanifold.

The second concept is about a subcomplex of the $n$-th chromatic subdivision
of a $k$-simplex. We define the non-boundary complex of $Ch^{n}(s^{k})$ as the
simplicial complex consisting of those simplices in $Ch^{n}(s^{k})$, each
vertex of which has a carrier $s^{k}$. In other words, the non-boundary
complex can be obtained from $Ch^{n}(s^{k})$ by removing all those n-simplices
that have some vertices in the boundary of $Ch^{n}(s^{k})$. In the example of
$Ch^{2}(s^{2})$ shown in Figure 2, the non-boundary complex is the simplicial
complex with white color. We want to sort the n-simplices of a non-boundary
complex into a sequence. The following lemma proves that the non-boundary
complex is a pseudomanifold.

###### Lemma 5.13.

The non-boundary complex of any iterated chromatic subdivision of a
$k$-simplex is a pseudomanifold.

###### Proof.

Let $Ch^{n}(s^{k})$ be an iterated chromatic subdivision of a simplex $s^{k}$.
We prove this by induction on the number $n$. If $n=1$, then the non-boundary
complex has only one $k$-facet which is the central $k$-simplex of the
chromatic subdivision, and therefore is a pseudomanifold.

Assume that the non-boundary complex of $Ch^{n-1}(s^{k})$ is a pseudomanifold.
Then the chromatic subdivision of it will be a pseudomanifold. In other words,
those simplices in the non-boundary complex of $Ch^{n}(s^{k})$ reached from
some $k$-simplex in the non-boundary complex of $Ch^{n-1}(s^{k})$ are in one
equivalence class. Any remaining $k$-simplex is reached from some so-called
boundary $k$-simplex of $Ch^{n-1}(s^{k})$. Note that our definition of a
boundary simplex is different from that of other materials.

Let $\sigma$ be a boundary $k$-simplex of $Ch^{n-1}(s^{k})$, then we will show
that the non-boundary simplices of $Ch^{n}(s^{k})$ reached from $\sigma$ will
be in the same equivalence class. Let $V$ denote the set of vertex of $\sigma$
consisting of those whose carrier is $s^{k}$. In other words, $V$ are those
internal vertices of $\sigma$. Then there is a bijection $\rho$ between the
partitions of $\Pi$ whose first process set contains some vertex in $V$ and
the non-boundary simplices reached from $\sigma$. For each vertices set $S$
containing some vertex in $V$, $NBS(S)$ is defined to be $\\{\rho(Par)\\}$
where $Par$ is a partition of $\Pi$ and the first partition set is $S$.
$NBS(S)$ is the joining of a $|S|$-simplex and the chromatic subdivision of a
$(|\Pi|-|S|)$-simplex. Since the latter is a pseudomanifold, $NBS(S)$ is a
pseudomanifold. For each vertex $v\in V$, $NBS(v)$ is defined as the union of
all $NBS(S)$ where $v\in S$, as shown in Figure 3. The intersection between
$\sigma\uparrow\\{v\\}$ and $\sigma\uparrow\\{v\\}\bigcup V^{{}^{\prime}}$,
for some $V^{{}^{\prime}}\subseteq V$, is
$(\Xi\downarrow\\{v\\})(\sigma\uparrow\\{v\\}\bigcup V^{{}^{\prime}})$. In
other words, the intersection is a simplicial complex whose dimension is
$(k-1)$. Therefore, all simplices of $NBS(v)$ belong to the same equivalence
class. Each $NBS(v)$, where $v\in V$, contains $NBS(V)$ and therefore belongs
to the same equivalence class. The set $\\{NBS(v)\\}$ forms a covering of non-
boundary simplices of $Ch^{n}(s^{k})$ reached from $\sigma$, which are
therefore in the same equivalence class.

Figure 3. $NBS(v)$ in $Ch^{2}(s^{2})$

$NBS(v)$ in $Ch^{2}(s^{2})$

Then we will show that the equivalence class is the same regardless of which
boundary $k$-simplex $\sigma$ of $Ch^{n-1}(s^{k})$ is chosen. All simplices in
$Ch^{n-1}(s^{k})$ (including both non-boundary simplices and boundary
simplices) form a pseudomanifold since $s^{k}$ is a pseudomanifold. If $s$ and
$s^{{}^{\prime}}$ are k-simplices of $Ch^{n-1}(s^{k})$, by definition, there
is a finite sequence $s=s_{1},s_{2},\cdots,s_{m}=s^{{}^{\prime}}$ of
k-simplices of $Ch^{n-1}(s^{k})$ such that $s_{i}$ and $s_{i+1}$ have an
$(n-1)$-face in common, for $1\leq i<m$. After a subdivision of the common
$(n-1)$-face, the central simplex will be an internal $(n-1)$-face which is a
common $(n-1)$-face of two non-boundary simplices reached from $s_{i}$ and
$s_{i+1}$ respectively. Therefore, the non-boundary simplices reached from
$s_{i}$ and $s_{i+1}$ are in the same equivalence class. We can get the same
result for $s$ and $s^{{}^{\prime}}$, which means that there exists one unique
equivalence class for all non-boundary simplices of $Ch^{n}(s^{k})$.

∎

####  5.2.5. Finalization after phase 1(Stage 3, 4)

We return to the discussion of different categories related to an intersection
facet $s^{k}$. We will discuss the category whose carrier is $s^{k}$, and then
the category whose carrier is some subsimplex $s^{k-1}$. Finally, an induction
is given.

The first step is to consider the category whose carrier in $Ch(\mathcal{I})$
is the $k$-facet $s^{k}$. By Lemma 5.13, we know that the $k$-simplices in
this category form a pseudomanifold. It is possible to enumerate these
$k$-simplices in a finite sequence $s_{0},s_{1},....,s_{q},....s_{e}$ and to
find a sequence $s_{1}^{{}^{\prime}},....,s_{q}^{{}^{\prime}},....$ of
$(k-1)$-simplices of the internal complex such that for $q\geq 1$,
$s_{q}^{{}^{\prime}}$ is a face of $s_{q-1}$ and also a face of $s_{q}$. Note
that we only require every $k$-simplex to appear in this sequence, as a
consequence of which a $k$-simplex may appear multiple times. The shared
$k$-simplex that makes $s^{k}$ compatible is chosen to be the last $k$-simplex
$s_{e}$ of the sequence.

The adversary will maintain a finalization invariant after processing the
n-cliques whose projections are in $s_{q}$: for each set with some opposite
label $(U^{{}^{\prime}},V^{{}^{\prime}})$ in the union of the n-cliques whose
projections $prj(\sigma)$ are in $s_{0}\cup s_{1}\cup s_{2}....\cup s_{q}$,
the outermost layer of the set can be expressed as the output configuration of
$s_{q}$ using $Protocol(U^{{}^{\prime}},V^{{}^{\prime}})$. The problem is that
the added layers of different output configuration may be adjacent to the same
vertex whose output value is therefore impossible to decide. To avoid the
conflict of terminated values in further induction, for those n-cliques whose
projections have not appeared in $s_{0}\cup s_{1}\cup s_{2}....\cup s_{q}$,
any undefined path between non-adjacent added layers should have a large
length. This can be achieved by increasing the number of layers added when
processing $s_{q}$.

Consider the n-cliques $\sigma$ whose projections $prj(\sigma)$ are in
$s_{0}$. The adversary adds some layers of projection values $prj(\sigma)$ to
each set. In fact, this is the first step for any terminated set, which will
be repeated many times in the following discussion. Let $v$ be a terminated
vertex with some opposite label $(U^{{}^{\prime}},V^{{}^{\prime}})$, and let
$v^{{}^{\prime}}$ be some vertex adjacent to $v$. The adversary will terminate
$v^{{}^{\prime}}$ with some value of the output configuration of $s_{0}$ using
$Protocol(U^{{}^{\prime}},V^{{}^{\prime}})$. We require that if the id of
$v^{{}^{\prime}}$ is in $s_{0}$, then it is terminated with the corresponding
value. This rule should apply to any termination with projection values. The
newly introduced output configurations are always valid since the task is
colorless. For those n-cliques $\sigma$ whose projections $prj(\sigma)$ are a
subsimplex of $s_{0}$, simply add layers of output configuration of the
corresponding subsimplex of $s_{0}$. The finalization invariant holds.

The adversary then processes the n-cliques whose projections are in $s_{1}$.
The terminated sets can be classified into three types: sets in n-cliques
whose projections are in $s_{0}$, sets in n-cliques whose projections are in
$s_{1}$, and sets at the intersection.

First, the adversary processes the sets in the n-cliques whose projections are
in $s_{0}$: add some layers of output configurations of $s_{1}$ using
$Protocol(U^{{}^{\prime}},V^{{}^{\prime}})$ to each set. This is possible
since the output configuration of $s_{1}$ using
$Protocol(U^{{}^{\prime}},V^{{}^{\prime}})$ is different from that of $s_{0}$
by the output value of only one vertex, denoted by $p$. Suppose that before
the operation, $s^{n}$ is a $n$-simplex partially terminated with the output
configuration of $s_{0}$. If $s^{n}$ has some terminated value of the process
$p$, then the adversary terminates the remaining vertices of $s^{n}$ with the
output configuration values of $s_{0}$ except the value of the process $p$,
i.e. the values of $s_{1}^{{}^{\prime}}$. If $s^{n}$ does not have any
terminated value of the process $p$, then the adversary terminates the
remaining vertices of $s^{n}$ with values of the output configuration of
$s_{1}$. The outermost layer will be the output configurations that contain
values in the output configuration of $s_{1}$.

Then we consider the sets in the n-cliques whose projections are in $s_{1}$.
The adversary adds some layers of projection values. In other words, the
adversary terminates the vertices adjacent to a terminated vertex with values
of $s_{1}$.

The remaining sets are those sets at the intersection of the n-cliques whose
projections are in $s_{1}$ and those whose projections are in
$s_{1}^{{}^{\prime}}$. That is, the projections of these sets will be in both
$s_{0}$ and $s_{1}$. Again, the adversary adds some layers of projection
values. If some newly terminated vertex is projected onto some simplex
$s_{prj}$ in $s_{0}\cup s_{1}$, it is terminated with some value of the output
configuration of $s_{prj}$. The adversary then adds some layers of
$s_{1}^{{}^{\prime}}$. The outermost layer has output configurations of
$s_{1}$ since $s_{1}^{{}^{\prime}}$ is a subsimplex of $s_{1}$. The adversary
will add layers of $s_{1}$ to keep the finalization invariant true.

Suppose that the adversary has processed the n-cliques whose projections are
in $s_{0}\cup s_{1}\cup....\cup s_{q-1}$ and the finalization invariant is
true. The adversary processes the sets in the n-cliques whose projections are
in $s_{q}$, which are divided into three types as above.

First, the adversary looks back to the sets whose projections are in
$s_{0}\cup s_{1}\cup....\cup s_{q-1}$. Such a set can be in multiple
n-cliques. The adversary adds some layers of output configurations of $s_{q}$,
which is possible since the output configuration of $s_{q-1}$ is different
from that of $s_{q}$ by the output value of only one vertex. Details have
already been given in the discussion of $s_{1}$.

Then we consider the sets totally in the n-cliques whose projections are in
$s_{q}$. The adversary adds layers of projection values. In other words, the
adversary will terminate the vertices adjacent to a terminated vertex with
some value of the output configuration of $s_{q}$.

The main obstacle is to add layers to the sets at the intersection of the
n-cliques whose projections are in $s_{q}$ and those whose projections are in
$s_{0}\cup s_{1}\cup....\cup s_{q-1}$. Now if $s_{q}$ has appeared in the
sequence before it(remember that we do not require that a $k$-simplex appear
only once in the sequence), then the adversary will treat these sets as sets
whose projections are in $s_{0}\cup s_{1}\cup....\cup s_{q-1}$. The adversary
adds some layers of output configurations of $s_{q}$.

If $s_{q}$ has not appeared in the sequence before it, the adversary has to
deal with sets at the intersection. In the general situation, the boundary is
not restricted to $s_{q}^{{}^{\prime}}$ as in the case of $s_{1}$ and this is
the reason why the general discussion will be much more complicated. By the
finalization invariant, for each terminated set in previous n-cliques, the
outermost layer of it has the output configurations of $s_{q_{1}}$. If a set
in the new n-cliques is connected to some previous set, then these sets should
be merged into a single set. However, the existing added layers are not
enough. This happens because some vertices on the previous boundary are no
longer boundary vertices when the adversary processes more n-cliques. More
specifically speaking, for a vertex $v_{o}$ after the second stage on the
boundary of an $n$-clique $\sigma$ whose projection is in $s_{q}$ and an
$n$-clique whose projection is in $s_{i}$ where $i<q$, the adversary has to
terminate some vertices in $\sigma$ reached from $v_{o}$ to ensure that the
internal layers of the existing added layers to $v_{o}$ will not be exposed.
Will this operation cause any conflict of assigned values in these n-cliques
whose projections are in $s_{q}$? Will the operation terminate more vertices
on the boundary so that the adversary has to look back to $s_{i}$ to fix the
same problem? Before we present what the adversary will do, we have to analyze
the terminated sets.

After the first stage, in which enough chromatic subdivisions are made, the
sets in an n-clique will either have a large active distance to the boundary
of the n-clique or have a zero active distance. Sets of the former type have
been discussed and will not affect the merging of sets. The sets we are more
interested in belong to the latter type, which means that after the second
stage the set will contain some terminated vertices on the boundary and the
sets from different n-cliques should be merged into a single one. These
terminated vertices on the boundary have output configurations of $s^{q}$. And
some layers have already been added to them on the boundary.

It is quite natural to think that the adversary can add layers to the merged
set using the values of the existing added layers on the boundary. But this
method does not work for our current adversarial strategy. Suppose that the
dimension of $s_{q}$ is $k$, a boundary simplex of $s_{q}$ is defined as a
subsimplex of $s_{q}$ whose dimension is $(k-1)$. This idea will not work for
sets containing vertices whose projections are in different boundary simplices
of $s_{q}$. In other words, a set can be connected to many existing terminated
sets, each of which is in the n-cliques whose projections are in $s_{j_{i}}$
where $j_{i}<q$. Recall that the intersection simplex can be terminated with
an opposite label and is not restricted by the assignment rule (2) since the
terminated configuration of such a simplex is one of its possible
configurations. There will be multiple choices of the existing added layers
that cause a conflict of output values to be used.

The solution to this disturbing issue is that we should limit the usage of the
existing added layers in a boundary simplex of $s_{q}$ to the undefined
vertices near it, rather than those vertices near another disjoint boundary
simplex. To achieve this goal, we have to reconstruct our adversarial strategy
described in Section 5.2.2. We place a restriction on the termination of a
vertex with some protocol configuration, just as on the termination with
opposite configuration. Once the adversary terminates a vertex with its
protocol configuration, it can not do it again until several rounds later.
This restriction can only cause a liveness issue which has been shown to be
impossible by Lemma 5.12 in the previous setting. However, as the proof of
Lemma 5.12 shows, the restriction on the second assignment rule will not cause
an infinite chain of queries. Due to the same reason, the new rule of
termination with protocol configurations will not cause an infinite chain of
queries, i.e., lead to a liveness problem. Perhaps we have to explain to the
readers why this rule is not introduced in Section 5.2.2. We impose a
restriction on the second assignment rule, since the definition of opposite
cliques with the label $(U,V)$ can only be used for those n-cliques having an
intersection with $Input(U,V)$. But this is not the situation for those
vertices terminated with some of its possible configurations. The new rule
will limit the projection of a terminated set to the open star of some simplex
on the boundary. Therefore, the adversary can terminate the undefined vertices
near the set using the values of the existing added layers on the boundary
without conflicts.

In our adversarial strategy, any vertex $v$ in an n-clique $\sigma$ terminated
with some opposite label $(U^{{}^{\prime}},V^{{}^{\prime}})$ will be connected
to some boundary vertex $v_{b}$ with $Input(U^{{}^{\prime}},V^{{}^{\prime}})$.
The n-clique $\sigma$ can be seen as the joining of a boundary simplex
$\sigma_{b}$ and a non-boundary simplex $\sigma_{nb}$. Let
$Carrier(v_{b},\sigma_{b})$ denote the carrier of $v_{b}$ in $\sigma_{b}$.

###### Lemma 5.14.

The carrier of a vertex $v$ not in $\sigma_{b}$ will be the joining of
$Carrier(v_{b},\allowbreak\sigma_{b})$ and $\sigma_{nb}$, or a larger simplex
that contains it.

###### Proof.

We will prove this result by contradiction. Suppose that the carrier of $v$ in
$\sigma$ is the join of any strict subsimplex of
$Carrier(v_{b},\allowbreak\sigma_{b})$ and $\sigma_{nb}$, denoted by
$\sigma_{des}$. There exists a shortest path $v_{0}=v_{b},v_{1},....v_{e}=v$
from $v_{b}$ to $v$. The vertex $v_{0}$ is not in $\sigma_{des}$ and $v_{0}$
is not adjacent to $v_{e}$ since $v_{e}$ is not a vertex in $\sigma_{b}$. We
know $e>1$. Both $v_{e-1}$ and $v_{e}$ are undefined vertices when $v_{e-2}$
is terminated. When $v_{e-1}$ is terminated after $r_{spe}$ rounds, there will
be some undefined vertices between $v_{e-1}$ and $v_{e}$, which is a
contradiction. ∎

Although we do not use the second assignment rule to add layers to the
terminated sets, the number of added layers has an upper bound, which means
that if enough subdivisions are made in the first stage, the added layers will
also satisfy the above lemma. Now, considering the vertices of a terminated
set after the second stage in $\sigma_{b}$, we will prove that these vertices
will be in the open star of some subsimplex of $\sigma_{b}$. In other words,
we will prove that there exists a terminated vertex whose carrier is $C_{a}$
such that each terminated vertex will have a carrier containing $C_{a}$.

###### Lemma 5.15.

Let $\sigma$ be an $n$-clique in $Ch^{r_{max}}(\mathcal{I})$. For each
terminated set after the second stage in $\sigma_{b}$, there exists a
terminated vertex whose carrier is $\sigma_{a}$ such that each terminated
vertex will have a carrier containing $\sigma_{a}$.

###### Proof.

Suppose that the carriers of two terminated vertices in $\sigma_{b}$ share a
common simplex $s_{s}$ in $\sigma_{b}$ but that no terminated vertex in
$\sigma_{b}$ has a carrier $s_{s}$, then the two vertices are connected by a
terminated path, each vertex having zero active distance to $s_{s}$. By our
adversarial strategy, some vertices in the subdivision of $s_{s}$ will
terminate in the second stage, which is a contradiction. ∎

Now we return to the discussion of n-cliques whose projections are in $s_{q}$.
Suppose that a terminated set $V_{t}$ merges with a previous set $V_{p}$. We
have to define a set of vertices in $V_{t}$ after the second stage. Let
$V_{o}$ be a set of vertices in $V_{t}$ on the boundary with $V_{p}$. Then
$V_{o}$ is a subset of $V_{t}$. Recall that a boundary simplex of $s_{q}$ is a
subsimplex of $s_{q}$. The adversary will use the existing layers added to
$V_{o}$ to terminate some vertices reached from $V_{t}$ whose projections are
in $s_{q}$ but not in $s_{q}^{{}^{\prime}}$.

If the projection of $V_{o}$ is within some boundary simplex of $s_{q}$, the
adversary will use the existing layers added to $V_{o}$. First, the adversary
adds layers of projection values to $V_{t}$. Let $V_{t}^{{}^{\prime}}$ denote
the newly terminated vertices. The difference here is that the adversary uses
the output configuration of the boundary simplex, rather than that of $s_{q}$.
The adversary can then add layers compatible with the existing layers on the
boundary: for each vertex $v$ in $V_{t}^{{}^{\prime}}$, the adversary
terminates the vertices reached from $v$ by an undefined path whose length
equals the number of existing layers. The concrete values are obtained from
the existing terminated layers added to $V_{o}$ on the boundary.

Layers added to a vertex in $V_{t}$ will not reach a vertex on the boundary.
This is true even for those vertices that are adjacent to a terminated vertex
on the boundary after the second stage. Suppose that after the second stage,
$v_{0}$ is a terminated vertex on the boundary and $v_{1}$ is a terminated
vertex not on the boundary. The two vertices are both undefined vertices after
the first stage. Let $\sigma$ denote an undefined $n$-simplex containing
$v_{0}$ and $v_{1}$ before stage 1. Note that at this time, $v_{1}$ may not
exist in $S^{t}$. The simplex $\sigma$ will be subdivided using the standard
chromatic subdivision enough times so that the active distance from $v_{1}$ to
the boundary will be 1 or a large number. So, after the second stage where
$v_{0}$ and $v_{1}$ are terminated, any path consisting of undefined vertices
from $v_{1}$ to a vertex on the boundary will have a long length. We give a
simple example to present our idea in Figure 4. When the adversary merges the
sets on the boundary, the added layers to $v_{1}$ will not reach the boundary,
which means that the adversary will not have to change the already terminated
vertices on the boundary or terminate some new vertices on the boundary.
Therefore, the adversary will not alternate infinitely between different sides
of the boundary, and it is valid for us to choose the form of induction to
process the terminated sets.

Figure 4. $v_{1}$ will have a large distance to the boundary

$v_{1}$ will have a large distance to the boundary

A more complicated situation is that the projection of $V_{o}$ will be in
multiple boundary simplices. More than one type of existing layer has been
added to $V_{o}$. At first, each vertex of the merged set will be mapped to a
projection vertex in $V_{o}$. This can be done by projecting a vertex $v$ to
$\sigma_{b}$ and then to boundary simplices. This is even valid for those
vertices whose projections are in some boundary simplex of $s_{q}$ which is
not a shared boundary simplex with $s_{0}\cup s_{1}\cup....\cup s_{q-1}$.
Still, the adversary has to add layers consisting of terminated values of the
boundary simplices. The terminated value of a vertex adjacent to some vertex
$v$ will be the output value of the projection vertex of $v$. Since there will
be some vertex $V_{sh}$ in $V_{o}$ terminated in the shared simplex of two
boundary simplices by Lemma 5.15, the terminated values added to the vertices
whose projection vertices are in $V_{sh}$ will serve as the intermediate part.
Therefore, the newly terminated vertices will not have any conflict of output
values. Let $V_{t}^{{}^{\prime}}$ denote the newly terminated vertices. The
adversary can add layers compatible with existing terminated vertices: for
each terminated vertex $v$ in $V_{t}^{{}^{\prime}}$, the adversary can
terminate the vertices reached from $v$ by an undefined path whose length
equals the number of existing added layers to its projection vertex. Concrete
values are also obtained from the existing terminated layers added to its
projection vertex on the boundary. Different types of added layers will not
cause any conflict since the existing added layers on the boundary do not have
a conflict of values. The output configurations of the outermost layer are
those of $s_{q-1}$. Finally, the adversary will add some layers of $s_{q}$.
All the added layers mentioned above will not cause any violation of the task
specification, since we are discussing the n-cliques in the same category and
the finalization invariant still holds.

By induction, finally the adversary will process the last $k$-simplex in the
sequence, i.e. the shared $k$-simplex. By the finalization invariant, the
output configurations of the outermost layer only contain values of the shared
output configuration of $Protocol(U,V)$ and
$Protocol(U^{{}^{\prime}},V^{{}^{\prime}})$. From now on, these shared output
configurations will be seen as output configurations with the label $(U,V)$.

The adversary will add more layers to connect the shared output configuration
to each output configuration in the n-cliques by $Protocol(U,V)$, dual to what
it has done. This time, the adversary will reverse the sequence of k-simplices
as $s_{e},s_{e-1},....,s_{q},....s_{0}$. When processing $s_{q}$, the
adversary will add some layers of output configurations of $s_{q}$ using
$Protocol(U,V)$ to all sets in the n-cliques whose projections are in
$s_{q}\cup s_{q+1}...\cup s_{0}$. If the projection of a set is both in
$s_{e}\cup s_{e-1},....\cup s_{q+1}$ and $s_{q}\cup s_{q+1}...\cup s_{0}$, the
new added layers will be applied to those vertices whose projections are in
$s_{q}\cup s_{q+1}...\cup s_{0}$ while leaving the other vertices untouched.

After the adversary processes $s_{0}$ in this way, we will discuss the sets in
the n-cliques whose projections are in $s_{q}$. If a set is completely
contained in these n-cliques, then the outermost layer of the set will be the
output configuration of $s_{q}$ using $Protocol(U,V)$, which is exactly what
we want. The sets whose projections are on the boundary of $s_{q}$ can be
divided into two types. If a set is on the boundary with the n-cliques whose
projections are in $s_{q+i}$ for some integer $i$, then the outermost layer of
the set will be the output configurations of $s_{q}$. But if a set is on the
boundary with the n-cliques whose projections are in $\sum s_{q-i}$ for a set
of integers $i$, then some new terminated vertices reached from $V_{o}$ will
be exposed as the outermost layer in the n-cliques whose projections are in
$s_{q}$. The adversary uses the same techniques as described in the previous
paragraphs. To accommodate these newly terminated vertices on the boundary,
the adversary can add layers by assigning values to the undefined vertices
reached from some vertex in $V_{t}^{{}^{\prime}}$ by an undefined path whose
length equals the number of layers added to its projection vertex. The
outermost layer consists of protocol configurations of $s_{q}$, since the
protocol configurations of two adjacent cliques are the same on their shared
boundary.

The last step is to add some layers to ensure that if some vertex $v$ of the
outermost layer is projected onto some simplex in the subdivision of $s^{k}$,
then it will use some value of the protocol configuration of this simplex as
its output. This is always possible by adding vertices of the required output
values directly, since the task is colorless. The reason for introducing this
step is explained in the following discussion.

The adversary now processes the categories whose carriers are facets of the
$(k-1)$-skeleton of $s^{k}$, denoted by $s^{k-1}$. These categories will not
overlap, as indicated by the red, purple, and yellow colors in Figure 2. This
can be proved by the active distances between their carriers. However, each of
these categories may have a shared boundary with the category whose carrier is
$s^{k}$. Before the adversary repeats what it has done to the category whose
carrier is $s^{k}$, it has to deal with those vertices on the boundary with
the n-cliques whose projections are in $s^{k}$. Note that the boundary between
different categories is not simply a simplex like the boundary of their
projections in $s^{k}$, but contains each n-clique whose projection is within
the boundary of their projections. As the reader can see, the adversary uses
similar techniques again. Stage 1 and stage 2 are the same as in the previous
category(including how many times the chromatic subdivisions are made). In
fact, what we have done is to bring stage 1 and stage 2 of all categories
forward to merge into single stage 1 and stage 2.

Since the adversary has processed the category whose carrier is $s^{k}$, some
n-cliques in the category whose carrier is $s^{k-1}$ will see some newly
terminated layers on the boundary. The outermost layer consists of values of
protocol configurations. But our procedure requires that, at the beginning,
the outermost layer consists of the output configurations of the opposite
clique with the label $(U^{{}^{\prime}},V^{{}^{\prime}})$ (rather than the
protocol configurations). The adversary will add layers compatible with
existing layers by assigning values to those undefined vertices reached from
some terminated vertex after the second stage by an undefined path whose
length equals the number of needed layers, similar to what the adversary has
done so many times. However, to recover the output configuration of the
opposite label $(U^{{}^{\prime}},V^{{}^{\prime}})$, the adversary will add the
same set of layers, but in reverse order. A key observation is that for each
terminated set in the n-cliques of the category whose carrier is $s^{k-1}$, if
it has some vertices on the boundary with the category whose carrier is
$s^{k}$, then the carrier of projections of this set is $s^{k}$ rather than
any subsimplex of $s^{k}$. By Lemma 5.14, the added layers will not violate
the carrier map.

Now, the required conditions of our procedure are satisfied. The adversary
will use techniques for the category with carrier $s^{k}$. As a consequence,
the outermost layer of the sets with the label
$(U^{{}^{\prime}},V^{{}^{\prime}})$ will be the protocol configurations of its
projections. Note that the projections here are projections to the carrier of
the category, that is, $s^{k-1}$ rather than $s^{k}$. Therefore, a vertex
shared by two categories can be projected onto different simplices in the
subdivision of $s^{k}$. To avoid any conflict of output values, the last step
is to add some layers to ensure that if a vertex of the outermost layer is
projected onto some simplex in the subdivision of $s^{k}$, it will use some
value from the protocol configuration of this simplex as its output. This is
possible since the task is assumed to be colorless.

After the procedure for a category, the layer addition operation will now be
used for those n-cliques in the category whose carrier is $s^{k}$ to eliminate
the impacts of the current category. After this, the outermost layers of the
sets with the label $(U^{{}^{\prime}},V^{{}^{\prime}})$ in n-cliques of the
category with carrier $s^{k}$ will still be their protocol configurations.

A general induction can be given. Suppose that the categories whose carriers
are facets of the $k-q+1$-skeleton of $s^{k}$ for some $0<q\leq k$ have been
processed and the outermost layer of the sets with the label
$(U^{{}^{\prime}},V^{{}^{\prime}})$ in the n-cliques of those categories will
be their protocol configurations. Let $s^{k-q}$ be the carrier of some
category. Then it has some shared boundary with some previous categories. To
create the required conditions of our procedure, the adversary has to add
layers compatible with newly terminated vertices. The new assigned values are
obtained from the existing layers on the boundary. The adversary then adds
layers in reverse order to recover the output configuration of the opposite
label $(U^{{}^{\prime}},V^{{}^{\prime}})$. Now, the procedure for a category
will be used. To avoid conflict of output values, some layers are added to
ensure that if a vertex of the outermost layer is projected onto some simplex
in the subdivision of $s^{k}$, it will use some value from the protocol
configuration of this simplex as its output. Finally, the operation of adding
layers will be used in previous categories to eliminate the impacts of the
current category. No task specification will be violated, as we have shown for
the category whose carrier is $s^{k-1}$. Until now, we have processed
categories, each of which has a carrier of a subsimplex of a $k$-facet.

In fact, the idea of alternating between protocol configurations and output
configurations of opposite cliques on the boundary will also be used to
connect the categories of different k-facets, including k-facets reached from
different initial configurations. We remind the reader that the input complex
$Input(U,V)$ contains all configurations in $Ch^{1}(\mathcal{I})$ reached from
some initial configuration in which the processes in $V$ satisfy the value
requirement $V$. The complex of intersections of $Input(U,V)$ and
$Input(U^{{}^{\prime}},V^{{}^{\prime}})$ in $Ch^{1}(\mathcal{I})$ can contain
$k$-facets reached from different initial configurations. But there is some
risk of safety problems. We have to show that the terminated values used in
alternating will not cause a violation of the carrier map. In short, the
output configurations the adversary will use in alternating are all obtained
from the already terminated layers on the boundary of two categories, and the
vertices to be terminated will have a larger or equivalent carrier.

We will use Lemma 5.14 to the shared boundary of two categories. Suppose that
two categories are adjacent and that the vertex $v_{o}$ in an $n$-clique
$\sigma$ is on the shared boundary of two categories after the second stage.
The existing layers added to $v_{o}$ have a carrier as the join of
$Carrier(prj(v_{o}),Ch(\mathcal{I}))$ and $\sigma_{nb}$. The projection of the
newly terminated vertices has a carrier containing
$Carrier(prj(v_{o}),Ch(\mathcal{I}))$. The newly terminated vertices reached
from $v_{o}$ have a larger carrier than(or an equal carrier as) the join of
$Carrier(prj(v_{o}),\mathcal{I})$ and $\sigma_{nb}$. Therefore, the existing
layers to $v_{o}$ on the boundary can be used without any violation of the
task specification.

Finally, after processing all intersection facets of all possible opposite
labels $(U^{{}^{\prime}},V^{{}^{\prime}})$, the adversary arrives at stage 4
where it will fill the gap between the sets of different labels. By our
construction, the outermost layers of the sets with label
$(U^{{}^{\prime}},V^{{}^{\prime}})$ in each n-cliques of each category will be
their protocol configurations. Therefore, the adversary uses the value of the
protocol configuration for each undefined vertex $v$ in $S^{t}(\sigma)$ for
each n-clique $\sigma$ in $Ch^{r_{max}-1}(C)$ where $C\in Input(U,V)$. Each
vertex in $S^{t}$ reached from $Input(U,V)$ has been terminated with an output
value, which means that the adversary has constructed a protocol for
$Input(U,V)$. In phases $\varphi\geq 2$, the adversary will respond to queries
according to the protocol and therefore will not cause safety or liveness
problems. Eventually, the prover will choose a configuration in which every
process has terminated to end some phase and lose in the next phase.

We summarize the above results into a theorem.

###### Theorem 5.16.

For a general colorless task$(\mathcal{I},\mathcal{O},\Delta)$, there exists
an adversary that can finalize after the first round to win against any
restricted extension-based prover if and only if there exists a protocol for
each $Input(U,V)$ and all intersection simplices in the standard chromatic
subdivision of all initial configurations are compatible.

###  5.3. Augmented extension-based proofs

Now we consider augmented extension-based proofs that allow assignment queries
$(C,P,f)$. The prover has to reply whether there exists a $P$-only schedule
from the configuration $C$ such that the output values of $Q\subseteq P$
satisfy the requirement of $f$. The prover can submit assignment queries to
obtain all possible output configurations reached from a $k$-simplex $s^{k}$
in $Ch(\mathcal{I})$ at the intersection of $\Xi(C\uparrow U_{1})$ and
$\Xi(C\uparrow U_{2})$. Then after the first phase, the output configurations
for a $k$-simplex reached from $s^{k}$ by the protocols constructed for
$Input(U_{1},V_{1})$ and $Input(U_{2},V_{2})$ should be these configurations.
Will this new type of query give the prover more power and a stronger
condition for finalization be required? The answer to this question is no. In
this section, we will show that the adversary can answer the assignment
queries while maintaining the invariants and guaranteeing that the response of
augmented extension-based proof will not be violated.

For each n-clique $\sigma$ in $Ch^{r_{max}}(\mathcal{I})$, any possible
terminated configuration in $S^{t}(\sigma)$ after phase 1 is a subsimplex of
the protocol configuration of $\sigma$, a subsimplex of the output simplex of
its opposite clique with $(U^{{}^{\prime}},V^{{}^{\prime}})$, or a subsimplex
of some output configuration introduced in finalization, as described in
Sections 5.2.4 and 5.2.5. In previous sections, we have not discussed the
configurations introduced in finalization, since the proof of correctness will
not depend on the concrete values of output configurations. But now to answer
the assignment queries, we have to look into the details.

For each n-clique $\sigma^{{}^{\prime}}$ in the same category, let
$prj(\sigma^{{}^{\prime}})$ denote the projection of $\sigma^{{}^{\prime}}$
into the carrier of the category. The newly terminated configurations in
$\sigma$ will contain output configurations whose values are chosen from the
protocol configuration or the output configuration of the opposite clique of
$prj(\sigma^{{}^{\prime}})$. We define the finalization configurations of a
category as these output configurations, since they are shared by each
n-clique $\sigma$ in the category. But this is not enough for those n-cliques
on the boundary with other categories. We have to analyze this in a more fine-
grained way. For each n-clique $\sigma$ in $Ch^{r_{max}-1}(Input(U,V))$, let
$s^{l}$ denote a $l$-simplex with the label
$(U^{{}^{\prime}},V^{{}^{\prime}})$ reached from $\sigma$. By invariant (2),
we know that there exists a terminated path from some $v_{o}$ on the boundary
with other categories to $s^{l}$. The finalization configurations of $s^{l}$
will also contain the restrictions to the processes in $s^{l}$ of the
finalization configurations of each category that contains the vertex $v_{o}$.

By our adversarial strategy described in Sections 5.2.4 and 5.2.5, the
finalization configurations of the $l$-simplex $s^{l}$ in $\sigma$ will
contain each possible output configuration of $s^{l}$. Note that we do not
require each finalization configuration of $s^{l}$ to appear as a terminated
configuration in stage 3 when the adversary is constructing a protocol for
$Input(U,V)$. We will show that each finalization configuration of $s^{l}$
will not cause any violation of the task specification. If the category $C$
contains the n-clique $\sigma$, the finalization configurations of this
category will not cause any violation of the task specification according to
the definition of a category. If the category $C$ that contains the vertex
$v_{o}$ does not contain $\sigma$, there exists a terminated path from $v_{o}$
to $s^{l}$. We can see the finalization configurations of $C$ as the existing
layers added to $v_{o}$ on the boundary, and therefore these output
configurations will not cause any violation of the task specification when
applied to $s^{l}$, as we have shown that alternating between the protocol
configurations and the output configurations of opposite cliques will not
cause a safety issue. An important property of finalization configurations is
that the space formed by all finalization configurations is a connected space.
In other words, each finalization configuration can be connected to the output
configuration of the opposite clique of $s^{l}$ by some path of finalization
configurations, since the carrier of each category is compatible by
assumption.

Suppose that the invariants hold before an assignment query $(C,P,f)$ in phase
1 and $C$ is reached from some configuration in $Input(U,V)$. By invariant
(1), we know that the states of processes in $P$ will correspond to a simplex
in $S^{r}$, where $r\leq t$. If the round number $r$ is less than $r_{max}$,
the result of a single assignment query $(C,P,f)$ can be generated from the
results of a set of assignment queries $(C^{{}^{\prime}},P,f)$ where
$C^{{}^{\prime}}$ is a $k$-simplex reached from $C$ in
$Ch^{r_{max}}(\mathcal{I})$. Therefore, we will only discuss the assignment
queries where $r\geq r_{max}$ and the configuration $C$ is reached from some
n-clique $\sigma$ in $Ch^{r_{max}}(\mathcal{I})$. Let $R^{t}$ denote the
subcomplex of $S^{t}$ consisting of all simplices $s^{k}$ reached from this
simplex by a $P$-only $(t-r)$-round schedule. We will discuss the k-simplices
in $R^{t}$.

Analysis is relatively straightforward when a desired configuration has
already been reached or when all configurations are determined but no desired
configuration has been reached. Note that the output configuration here is the
protocol configuration or the output configuration of the opposite clique(not
including the finalization configurations). If there exists a $k$-simplex
$\tau$ in $R^{t}$ having some vertex $v$ terminated with label $(U^{d},V^{d})$
and the output configuration with label $(U^{d},V^{d})$ satisfies $f$, then
the adversary can submit a chain of queries from this $\tau$ to itself. By
Lemma 5.12 this chain of queries must be finite and end with a $(k-1)$-simplex
with label $(U^{d},V^{d})$. The output values of the join of this simplex and
$v$ satisfy $f$. Because the adversary does not change $\Delta$ and will not
change the defined values once they have been set, the invariants will still
hold. If each $k$-simplex $\tau$ in $R^{t}$ has some terminated vertices and
the output configuration of this label $(U^{t},V^{t})$ does not satisfy the
requirement of $f$, then no $k$-simplex reached from $\tau$ will satisfy $f$.
This is because in the second stage of Section 5.2.4, each vertex adjacent to
a terminated vertex will be terminated with the same label. Each $k$-simplex
reached from $\tau$ will terminate with the output configuration with the
label $(U^{t},V^{t})$.

Therefore, we will only discuss the $k$-simplices in $R^{t}$ that do not have
a terminated vertex and $R^{t}$ contains at least one undefined $k$-simplex.
For each undefined $k$-simplex $\tau\in R^{t}$, let $A_{\tau}$ denote the
subcomplex of $S^{t}$ that contains vertices at a distance of at most 1 to
each vertex in $\tau$. In other words, $A_{\tau}$ consists of all n-simplices
that contain $\tau$. We will classify the different $\tau$ into several cases
according to the status of the vertices of $A_{\tau}$. In cases 1 and 2, some
vertices of $A_{\tau}$ have been terminated. These two situations are quite
similar to the situation in which a vertex in $\tau$ is terminated. Therefore,
the argument given in the last paragraph will be used again, and no
finalization configurations are involved. In cases 3 and 4, all the vertices
in $A_{\tau}$ are undefined. In case 3 where the surrounding vertices of
$\tau$ are not defined, we will show that $\tau$ will be separated from other
terminated sets. By invariant (2), the output configurations reached from
$\tau$ are the finalization configurations with $b$, where $b$ is some
possible label of some subset of $\tau$. In case 4, some vertex in $\tau$ is
adjacent to a terminated vertex with the label $(U^{d},V^{d})$. Therefore, in
addition to the finalization configurations with $b$, where $b$ is some
possible label of some subset of $\tau$, the finalization configurations with
the label $(U^{d},V^{d})$ are also possible.

Case 1: There is a $k$-simplex $\tau$ in $R^{t}$, some vertex in $A_{\tau}$ is
terminated with the label $(U^{d},V^{d})$ and the output configuration with
the label $(U^{d},V^{d})$ satisfies $f$. The adversary will submit a chain of
queries such that some $k$-simplex reached from $\tau$ will terminate with the
desired output configuration that satisfies the function $f$. Let $(U,v)$ be
the protocol label and let $(U^{{}^{\prime}},V^{{}^{\prime}})$ be some
opposite label. We choose to use the query chain to accommodate both cases:
$(U^{d},V^{d})$ = $(U,V)$ or $(U^{d},V^{d})$ =
$(U^{{}^{\prime}},V^{{}^{\prime}})$ as queries will not violate the
invariants. The adversary can return the schedule from configuration $C$ to
this $k$-simplex.

Case 2: There is a $k$-simplex $\tau$ in $R^{t}$ and some vertex in $A_{\tau}$
is terminated with a label $(U^{d},V^{d})$, but the projection into $P$ of the
output configuration with the label $(U^{d},V^{d})$ does not satisfy $f$. Any
simplex in a subdivision of $\tau$ will be adjacent to this terminated vertex.
In stage 2 of Section 5.2.4, each undefined vertex adjacent to a terminated
vertex will be terminated with its label. Therefore, all configurations
reached from the $k$-simplex $\tau$ will have the label $(U^{d},V^{d})$ and
are therefore not possible to satisfy the function $f$.

Case 3: There is a $k$-simplex $\tau$ in $R^{t}$, every vertex in $A_{\tau}$
is undefined and all vertices adjacent to $\tau$ are undefined.

Case 3.1: If the label $(U,V)$ is a possible label for $\tau$ and the
projection into $P$ of the output configuration with the label $(U,V)$
satisfies $f$, the adversary can subdivide $S^{t}$ and increase $t$ three
times. We define the simplex $\rho=\\{(i,\vec{\tau}):i\in Id(\tau)\\}$ in
$Ch(\tau)$ as the central simplex of the standard chromatic subdivision. Then
the central simplex of $Ch^{3}(\tau)$ will have an active distance of at least
3 to all terminated configurations with other labels. The adversary can
terminate a simplex reached from this central simplex with the label
$(U^{d},V^{d})$ and return the schedule from $C$ to this simplex.

Case 3.2: The discussions in case 3.1 are also true when
$(U^{{}^{\prime}},V^{{}^{\prime}})$ is a possible label for only a subset
$\tau^{{}^{\prime}}$ of $\tau$. If the output configuration with label
$(U^{{}^{\prime}},V^{{}^{\prime}})$ satisfies the function $f$, the adversary
will still subdivide $S^{t}$ and increase $t$ three times. In fact, any
simplex in $Ch^{3}(\tau)$ will have an active distance of at least 3 to all
terminated configurations with other labels. We will choose a simplex
$s_{int}$ in $Ch^{3}(\tau)$ that has some subsimplex in $\tau^{{}^{\prime}}$.
The adversary can then terminate a simplex reached from $s_{int}$ with the
label $(U^{d},V^{d})$ and return the schedule from $C$ to this simplex.

Now, we have to discuss the output configurations introduced in the
finalization. If some finalization configuration $s_{o}$ of $\tau$ with the
label $(U^{{}^{\prime}},V^{{}^{\prime}})$ satisfies the function $f$, then the
adversary will construct $s_{o}$. First, the adversary will construct a
simplex $s_{int}$, as in the last paragraph. By the property of finalization
configurations, the adversary can construct a path $l$ from $s_{int}$ to the
desired configuration $s_{o}$ using rule (2). The adversary will ensure that
the configuration $s_{o}$ is far enough from other terminated sets. The
adversary has constructed the output configuration $s_{o}$ that satisfies the
function $f$. But it can not stop here since it has terminated some vertices
with label $(U^{d},V^{d})$ but not with the values of opposite clique with
label $(U^{d},V^{d})$, while this is the most basic assumption of our
interaction progress of extension-based proofs. The adversary will terminate
the vertices reached from the simplex $s_{o}$ by a path $l$ such that the
outermost layer of the terminated vertices will be the output configuration of
the opposite clique. This is possible since each $n$-simplex containing $\tau$
is included in $A_{\tau}$. After this operation, the output configurations on
the path from $s_{int}$ to $s_{o}$ will be sealed. The adversary will return
the schedule from $C$ to the configuration $s_{o}$. Since we have constructed
a path to any terminated simplex, invariant (2) will remain true.

Case 3.3: For each possible label $(U^{{}^{\prime}},V^{{}^{\prime}})$ of any
subset of $\tau$, the projections to $P$ of all finalization configurations
with label $(U^{{}^{\prime}},V^{{}^{\prime}})$ do not satisfy the function
$f$. Even if the projection to $P$ of the output configuration with an
opposite label $(U^{{}^{\prime}},V^{{}^{\prime}})$ satisfies the function $f$,
the adversary cannot simply terminate some simplex reached from $\tau$ with
the label $(U^{{}^{\prime}},V^{{}^{\prime}})$ since the adversary has to
maintain the invariant (2) which says that there must be a terminated path to
some existing simplex with the label $(U^{{}^{\prime}},V^{{}^{\prime}})$.
However, it is not safe to say that there will be no simplex that is reached
from $\tau$ and terminated with such a label
$(U^{{}^{\prime}},V^{{}^{\prime}})$, and therefore satisfies the function $f$.
In fact, there may be more possibilities, such as finalization configurations.
In previous work (AAE+, 19), the adversary will terminate all vertices reached
from $\tau$ with their protocol configurations to eliminate ambiguity. If we
adopt their method, it will look like this: since all vertices in $\tau$ are
not adjacent to the terminated vertices, the active distance between $\tau$
and every terminated configuration is at least 1. The adversary can subdivide
$S^{t}$ and increase $t$ three times so that all simplices reached from $\tau$
have an active distance of at least 3 to any terminated configuration. The
adversary will terminate all vertices with the label $(U,V)$ to ensure that
they do not terminate with the label $(U^{{}^{\prime}},V^{{}^{\prime}})$ in
the later interaction. But this method does not work for our adversarial
strategy, since it can generate a set that is too large to contain all
vertices in the subdivision of an intersection $k$-facet. Recall that in
Section 5.2.5, we introduce a new rule for terminating a vertex with its
protocol configuration. We will prove that any simplex reached from $\tau$
will not terminate with label $(U^{{}^{\prime}},V^{{}^{\prime}})$ using the
restriction of the second assignment rule.

If some $k$-simplex reached from $\tau$ is terminated with the label
$(U^{{}^{\prime}},V^{{}^{\prime}})$, the adversary has to find a terminated
path from the exterior of $A_{\tau}$ to $\tau$. We will prove that this path
is impossible and therefore all configurations reached from the $k$-simplex
$\tau$ will not have the label $(U^{{}^{\prime}},V^{{}^{\prime}})$. Let
$S_{\tau}$ denote the simplices in $S^{t}$ consisting of vertices that are
adjacent to some vertex in $\tau$ but are not included in $\tau$. The vertices
of $S_{\tau}$ are undefined by assumption. We will prove by contradiction that
it is impossible for any vertex $v$ in the subdivision of $\tau$ to have the
label $(U^{{}^{\prime}},V^{{}^{\prime}})$. The key idea of the proof is that
the vertices of $\tau$ and the vertices terminated with
$(U^{{}^{\prime}},V^{{}^{\prime}})$ in $S^{t}$ are separated by $S_{\tau}$.
The restricted application of rule 2 will only increase the distance in
further subdivisions.

Assume that the vertex $v_{n}$ is the first vertex in the subdivision of
$\tau$ terminated with the label $(U^{{}^{\prime}},V^{{}^{\prime}})$. Then
there exists an earliest path $v_{0},v_{1},....v_{n}$ from some vertex $v_{0}$
in the subdivision of $S_{\tau}$ to $v_{n}$. Consider the moment when the
vertex $v_{n-2}$ is terminated in some $S^{t}$, $v_{n-1}$ is undefined. The
active distance between $v_{n-2}$ and the subdivision of $\tau$ is at least 2.
Let $S_{\tau}^{{}^{\prime}}$ denote the simplices of the current $S^{t}$
consisting of vertices that are adjacent to some vertex in the subdivision of
$\tau$, but are not included in the subdivision of $\tau$. The vertices of
$S_{\tau}^{{}^{\prime}}$ are not terminated with the label
$(U^{{}^{\prime}},V^{{}^{\prime}})$, since the path we are discussing is the
earliest path according to hypothesis. Therefore, $v_{n-1}$ must be in the
subdivision of $S_{\tau}^{{}^{\prime}}$ and $v_{n}$ must be in the subdivision
of $\tau$. After at least $r_{spe}$ rounds, any undefined path from the
subdivision of $S_{\tau}^{{}^{\prime}}$ to the subdivision of $\tau$ will have
a long length. It is not possible to terminate the vertex $v_{n}$ adjacent to
$v_{n-1}$ with the label $(U^{{}^{\prime}},V^{{}^{\prime}})$. A configuration
reached from the simplex $\tau$ is not possible to terminate with the label
$(U^{{}^{\prime}},V^{{}^{\prime}})$ and satisfy the function $f$.

Case 4: There is a $k$-simplex $\tau$ in $R^{t}$, every vertex in $A_{\tau}$
is undefined, but some vertex $v$ in $\tau$ is adjacent to a terminated vertex
$v^{{}^{\prime}}$ with the label $(U^{d},V^{d})$. Note that the vertex $v$
will not be in $A_{\tau}$ i.e. will not be adjacent to all vertices in $\tau$.
By invariants, the labels of two possible terminated vertices
$v^{{}^{\prime}}$ will be the same, since the active distances between the
configurations of two different labels are at least 3. Cases 4.1 and 4.2 are
the situations in which some configuration with the label $(U^{d},V^{d})$
satisfies the function $f$. Cases 4.3, 4.4 and 4.5 are situations in which no
configuration with label $(U^{d},V^{d})$ does.

Case 4.1: If the projection to $P$ of the output configuration with the label
$(U^{d},V^{d})$ satisfies $f$, the adversary can submit a chain of queries
corresponding to the solo execution of the vertex $v$. The vertex $v$ will
terminate with the label $(U^{d},V^{d})$ in later subdivisions of $\tau$. The
adversary can terminate some vertices adjacent to $v$ in a further subdivision
of $\tau$ with the label $(U^{d},V^{d})$ by submitting a chain of queries.
This is possible since according to Lemma 5.12 this chain of queries must be
finite and end with a $(k-1)$-simplex with label $(U^{d},V^{d})$. The
adversary will return the schedule from $C$ to the configuration reached from
$\tau$. Since we have constructed a path consisting of vertices terminated
with the label $(U^{d},V^{d})$ to the resulting simplex, the invariant (2)
will remain true. The invariant (3) is still true since after a subdivision,
the simplices reached from $\tau$ (including the constructed output
configuration) will have an active distance of at least 3 to any terminated
configuration with a label not $(U^{d},V^{d})$.

Case 4.2: If the label $(U^{d},V^{d})$ is an opposite label and the projection
to $P$ of some finalization configuration $s_{o}$ with the label
$(U^{d},V^{d})$ satisfies $f$, the adversary can submit a chain of queries
corresponding to the solo execution of the vertex $v$ which will be terminated
with the label $(U^{d},V^{d})$. The adversary will then use the techniques in
Case 3.2 to construct the desired configuration $s_{o}$ and return it as a
result.

Otherwise, the projection to $P$ of any possible output configuration with the
label $(U^{d},V^{d})$ does not satisfy the function $f$. We have to return to
the discussion of the possible labels of some subset of $\tau$, as in Case 3.

Case 4.3: If the label $(U,V)$ is a possible label for $\tau$ and the output
configuration with the label $(U,V)$ satisfies the function $f$, the adversary
can terminate a simplex $\sigma$ reached from the central simplex of
$Ch^{3}(\tau)$ with the label $(U,V)$. By assumption $v^{{}^{\prime}}$ is not
adjacent to each vertex in $\tau$, i.e. not a vertex in $A_{\tau}$, the
central simplex after several subdivisions will have an active distance of at
least 3 to all terminated configurations with opposite labels. The adversary
can return this simplex $\sigma$.

Case 4.4: If $(U^{{}^{\prime}},V^{{}^{\prime}})$ is a possible label for only
a subset $\tau^{{}^{\prime}}$ of $\tau$ and the output configuration with the
label $(U^{{}^{\prime}},V^{{}^{\prime}})$ satisfies the function $f$, the
adversary can generate a terminated path within $\tau$. A difference here from
Case 3 is that all vertices in $\tau^{{}^{\prime}}$ should not be adjacent to
a single terminated vertex with the label $(U^{d},V^{d})$. Otherwise, it
should be discussed in Case 4.5. The adversary can terminate some internal
simplex reached from $\tau$ with the label $(U^{{}^{\prime}},V^{{}^{\prime}})$
just as it will do in Case 3. The adversary can return the schedule from $C$
to this simplex, and all invariants will remain. Furthermore, if the
projection to $P$ of any possible output configuration of $\tau$ with the
label $(U^{{}^{\prime}},V^{{}^{\prime}})$, denoted by $s_{o}$ can satisfy the
function $f$, then the adversary will first terminate an internal $k$-simplex
$s_{int}$ with the output configuration of the label
$(U^{{}^{\prime}},V^{{}^{\prime}})$. By the property of possible output
configurations, we can construct a path from $s_{int}$ to $s_{o}$ by rule (2).
The adversary has constructed the output configuration $s_{o}$ that satisfies
the function $f$. Again, it cannot stop here, since it has terminated some
vertices not with the values of opposite clique. The operation of terminating
vertices reached from $s_{o}$ in case 3.2 will be repeated here.

Case 4.5: For each possible label $(U^{{}^{\prime}},V^{{}^{\prime}})$ of any
subset of $\tau$, projection into $P$ of any possible configuration of $\tau$
with label $(U^{{}^{\prime}},V^{{}^{\prime}})$ does not satisfy the function
$f$. Then, for the same reason as in Case 3.3, it is not possible to terminate
any configuration reached from the simplex $\tau$ with values that satisfy the
function $f$.

After checking each $k$-simplex in $R^{t}$, the adversary is able to answer
the assignment query. If the adversary manages to find an output configuration
in the subdivision of some $k$-simplex $\tau$, it can return the schedule from
$C$ to it. But if each $k$-simplex $\tau\in R^{t}$ cannot reach a
configuration that satisfies the function $f$, the adversary will return
$NULL$. By the strategy described above, the result of assignment queries will
not be violated. If an assignment query returns a schedule, the schedule will
remain valid in the later interaction, since the adversary will not change
$\Delta(v)$ once it has been set. On the other hand, if the assignment query
returns $NULL$, we have already proved that any configuration reached from $C$
will not satisfy the function $f$.

###### Lemma 5.17.

No assignment queries made in phase 1 will be violated.

Note that in all circumstances, the invariants will hold after the assignment
query, and all terminated vertices with an opposite label
$(U^{{}^{\prime}},V^{{}^{\prime}})$ can be seen as terminated with values from
the opposite cliques. Furthermore, since each output configuration added in
the execution of an assignment query is obtained from finalization
configurations, no task specification will be violated after an assignment
query.

Before proceeding to the next section, we want to talk about something
proposed in (BE, 21). In the original proof in (AAE+, 19), one of the
invariants guarantees that any two vertices terminated with different output
values are sufficiently far apart in $S^{t}$, which means that at the end of
phase 1 no clique in $S^{t}$ contains vertices that output different values.
In (BE, 21) it is pointed out that it is impossible to maintain this invariant
when the prover is allowed to submit assignment queries, since if so, the
adversary will tell the prover that it can solve the consensus task. What they
do to fix this issue is that the output configurations with two different
values are allowed in the interaction of phase 1. We can interpret this
solution in a simpler way using our consequence: output configurations
introduced in the finalization after phase 1 have to be and can be used in the
interaction procedure when the assignment queries are allowed.

###  5.4. Finalization after phase r

We have discussed the conditions for the finalization after the first phase.
But will we have to finalize in the latter phases when dealing with more
complicated tasks, e.g. tasks more difficult than $(n,2)$-set agreement? As
described in the definition of extension-based proofs, $\Delta$ can be
finalized after any phase $r$.

But we face a new challenge when discussing the finalization after the phase
$r$. Before we go directly to the finalization after phase $r$, it is better
to discuss the finalization after phase two to clarify the differences. Take
the 4-process task as an example. The input simplex
$Input(\\{v_{0},v_{1}\\},\\{0,0\\})$ is the joining of a 1-simplex $s^{top}$
and the chromatic subdivision of a 1-simplex $s^{bot}$. Suppose that there
exists no restricted protocol for the complex
$Input(\\{v_{0},v_{1}\\},\\{0,0\\})$, but a restricted protocol for each
3-simplex in $Input(\\{v_{0},v_{1}\\},\\{0,0\\})$ respectively. In previous
sections, we used the opposite cliques to obtain the terminated value of a
vertex with an opposite label. If some n-clique is reached from some n-simplex
$C_{1}$ in $Ch(\mathcal{I})$ by a schedule $\alpha$, then its opposite clique
is defined as the n-simplex reached from $C_{2}$ in $Ch(\mathcal{I})$ by
$\alpha$, where $C_{2}$ is calculated from $C_{1}$ according to some rule in
Section 5.2.1.

Let $s^{n}$ be an n-simplex reached from the join of $s^{top}$ and a 1-simplex
$C_{1}$ by schedule $\alpha$. It seems quite natural to define the opposite
clique of $s^{n}$ as the configuration reached by $\alpha$ from the join of
$s^{top}$ and $C_{2}$, where $C_{2}$ is calculated from $C_{1}$. However, the
third requirement for an opposite clique may not be satisfied. In fact, this
has happened before in the proof of Lemma 5.7 in which we solve this problem
by assuming $r_{max}\geq 2$. Perhaps we should recall the details of Lemma 5.7
and present the idea behind the differences. $C_{2}$ is not the opposite
clique of $C_{1}$ as some processes $P$ will see different sets of input
values. But the second partition of $\Pi$ starts with a set of processes that
contains some intersection process of $C_{1}$ and $C_{2}$ that eliminates the
mismatch of $P$. This argument does not work here: not each intersection
vertex can help to eliminate the mismatch. More specifically, the vertices in
$s^{top}$ cannot help to eliminate the mismatch. In Figure 5, we give a
simpler example of a 3-process task which still presents our ideas. The
opposite clique of a 2-simplex of red color satisfies the third requirement,
while the opposite clique of the 2-simplex of blue color does not.

Figure 5. Opposite cliques in $Input(\\{v_{0}\\},0)$ of a 3-process task

Opposite cliques in $Input(\\{v_{0}\\},0)$ of a 3-process task

For each pair $(U,V)$, the input complex $Input(U,V)$ can be seen as the
joining of a $|U|$-simplex $s^{top}$ and the chromatic subdivision of a
$|\Pi-U|$-simplex. $Input(U,V)$ can be further divided into a set of input
complexes, each of which corresponds to a subset of $(\Pi-U)$. Suppose that
there exists a protocol for each such input complex. To distinguish these
protocols, we assign a different label
$[(U,V),(U^{{}^{\prime}},V^{{}^{\prime}})]$ to each protocol, where
$U^{{}^{\prime}}$ is a subset of the process set $(\Pi-U)$ and is the first
process set to execute. In other words, the label is now a list of pairs
$(U,V)$.

Let $s^{n}$ be an n-simplex reached from the join of $s^{top}$ and a
$|\Pi-U|$-simplex $C_{1}$ by the schedule $\alpha$. We define the opposite
clique of $s^{n}$ as an n-simplex reached by $\alpha$ from the join of
$s^{top}$ and $C_{2}$ where $C_{2}$ is calculated from $C_{1}$. An n-clique
whose intersection simplex is in $s^{top}$ may have an opposite clique with a
larger carrier, as the example shows. Note that using the techniques in the
proof of Lemma 5.7, other n-cliques will not have this issue. We introduce a
rule, which is referred to as the carrier rule in subsequent discussions. Let
$\sigma$ be an n-clique in $Ch^{r_{max}-1}(Input(U,V))$. The vertices in
$\sigma$ can be divided into two types: intersection vertices and internal
vertices. The intersection simplex consisting of intersection vertices is in
$s^{top}$. If some subsimplex $\tau$ of $\sigma$ has a smaller carrier in the
opposite clique, then it is not safe to use the values of the opposite clique
to terminate the vertices in the subdivision of $\tau$. Instead, the vertices
in the subdivision of $\tau$ will terminate with the value of some
intersection vertex. The intersection vertex is chosen to be the projection of
$\tau$ to the intersection simplex. There will be no violation of the task
specification, since the intersection vertices have only seen the input values
of the processes in $U$, which all the vertices in $Input(U,V)$ have seen, and
the task is assumed to be colorless. We have to show that the carrier rule
will not cause any conflict of values. Recall that the opposite cliques of two
n-cliques sharing some vertex will share the vertex with the same process id.
If some other n-clique $\sigma^{{}^{\prime}}$ contains a vertex $v$ terminated
by the carrier rule, then by the property of opposite cliques, the vertex $v$
will also have a larger carrier in the opposite clique of
$\sigma^{{}^{\prime}}$. This means that $v$ will terminate with the carrier
rule, and the terminated value will be identical since the projection to
$s^{top}$ will be the same vertex.

So what is the difference of phase 1 when the restricted protocol for
$Input(U,V)$ is replaced by a sequence of restricted protocols for
$Input((U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$? We have to check whether the
previous results can still be used. First, we will show that Lemma 5.7 can be
used for these subprotocols: if an n-clique $\sigma$ has an intersection with
the input complex with some label $[(U,V),(U^{{}^{\prime}},V^{{}^{\prime}})]$,
then there exists an opposite clique of $\sigma$ with this label. Suppose that
an n-clique $\sigma$ has some intersection vertices with
$Input((U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$. We will use its opposite
clique $\sigma^{{}^{\prime}}$ with the label $(U,V)$ to construct its opposite
clique with the label $(U,V),(U^{{}^{\prime}},V^{{}^{\prime}})$. If
$\sigma^{{}^{\prime}}$ is in $Input((U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$,
then $\sigma^{{}^{\prime}}$ is the opposite clique of $\sigma$ with the label
$[(U,V),(U^{{}^{\prime}},V^{{}^{\prime}})]$. Otherwise, $\sigma^{{}^{\prime}}$
is in another input complex
$Input((U,V),(U^{{}^{\prime\prime}},V^{{}^{\prime\prime}}))$. Let $V_{int}$ be
the set of vertices shared by $\sigma$ and
$Input((U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$. Then $\sigma^{{}^{\prime}}$
will also contain $V_{int}$. Therefore, there exists an opposite clique of
$\sigma^{{}^{\prime}}$ with the label
$[(U,V),(U^{{}^{\prime}},V^{{}^{\prime}})]$. We will use the opposite clique
of $\sigma^{{}^{\prime}}$ as the opposite clique of $\sigma$.

Next, we prove that there will be no conflict of output values. If the vertex
$v$ is shared by two n-cliques having an intersection with
$Input((U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$, then the opposite cliques
with $(U,V)$ will share the vertex with the same process id. When the opposite
cliques with the label $(U,V)$ are both in or not in
$Input([(U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$, the opposite cliques with
the label $[(U,V),(U^{{}^{\prime}},V^{{}^{\prime}})]$ will share the vertex
with the same process id. If only one of the opposite cliques with label
$(U,V)$ denoted by $s^{oc}$ is in
$Input([(U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$, then the vertex $v$ will be
at the intersection of two input complexes. The opposite clique of $s^{oc}$
with the label $[(U,V),(U^{{}^{\prime}},V^{{}^{\prime}})]$ will not change the
intersection vertices, including the vertex $v$. Therefore, the opposite
cliques with the label $[(U,V),(U^{{}^{\prime}},V^{{}^{\prime}})]$ will still
share the vertex with the same process id. Therefore, the input complex
$Input(U,V)$ will be replaced by a sequence of input complexes
$Input((U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$ while our interaction
framework is kept valid.

After the second phase, the first two process set are determined, which means
that the adversary can limit its view to the subcomplex of $S^{t}$ reached
from the input complex labeled by $[(U,V),(U^{{}^{\prime}},V^{{}^{\prime}})]$.
The adversary can use the techniques in Section 5.2 to generate a protocol for
$Input((U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$. The condition required for
connecting output configurations of different labels is that each intersection
simplex must be compatible. The carrier rule will not affect these procedures
since the carrier rule will change the values of non-intersection vertices.
Only the output values of the intersection vertices are used to add layers to
the terminated sets.

###### Theorem 5.18.

For a general colorless task$(\mathcal{I},\mathcal{O},\Delta)$, there exists
an adversary that can finalize after the second phase and win against any
restricted extension-based prover if and only if there exists a protocol for
each $Input((U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$ and all intersection
simplices in the standard chromatic subdivision of all initial configurations
are compatible.

By Theorem 5.2, there exists a protocol for $Input(U,V)$ if and only if there
exists $\mathcal{O}_{\tau}^{i}$ for some $0\leq i\leq m$, such that the task
$(lk(\tau,\mathcal{I})$, $\mathcal{O}_{\tau}^{i}\backslash\tau$,
$\Delta_{\tau})$ has a protocol where $\tau$ is $s^{top}$ of $Input(U,V)$.
This task is a $|\Pi-U|$-processes task. Let $\rho$ denote $s^{top}$ of
$Input((U,V),\allowbreak(U^{{}^{\prime}},V^{{}^{\prime}}))$. Then there exists
a protocol for $Input((U,V),\allowbreak(U^{{}^{\prime}},V^{{}^{\prime}}))$ if
and only if there exists $(\mathcal{O}_{\tau}^{i})_{\rho-\tau}^{j}$ for some
$0\leq i\leq m$ and some $0\leq j\leq m^{{}^{\prime}}$, such that the task
$(lk(\rho,\mathcal{I})$,
$(\mathcal{O}_{\tau}^{i})_{\rho-\tau}^{j}\backslash(\rho-\tau)$,
$\Delta_{\rho})$ has a protocol. The choice of $i$ and $j$ can be arbitrary
when we discuss the existence of some
$Protocol((U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$. But if we are talking
about extension-based proofs, the choice of $i$ will be unique, since the
simplex $s^{top}$ of $Input(U,V)$ is compatible. This consequence can be
obtained from the proof of Lemma 5.1.

The decomposition of the protocol for
$Input((U,V),(U^{{}^{\prime}},V^{{}^{\prime}}))$ can continue. Suppose that
some input complex is labeled by $[(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})]$
where the process set $U_{i}\subseteq\Pi-\sum_{1}^{i-1}U_{l}$ for each $i$,
and all properties described above are satisfied. For each pair sequence, the
input complex $Input((U_{1},V_{1}),(U_{2},V_{2})\allowbreak...(U_{k},V_{k}))$
can be seen as the join of a $|\sum_{1}^{k}U_{i}|$-simplex $s^{top}$ and the
chromatic subdivision of a $|\Pi-\sum_{1}^{k}U_{i}|$-simplex. It will be
further divided into a sequence of input complexes, each of which corresponds
to a subset of the process set $\Pi-\sum_{1}^{k}U_{i}$. Suppose that there
exists a protocol for each such input complex. To distinguish these protocols,
we will assign a different label
$[(U_{1},V_{1}),\allowbreak...(U_{k},V_{k}),(U_{k+1},V_{k+1})]$ to each
protocol where $U_{k+1}$ is a subset of the process set
$(\Pi-\sum_{1}^{k}U_{i})$ and is the first process set in the subsequent
execution. For convenience, we will denote the old and new labels as $l_{o}$
and $l_{n}$. We will still define the opposite clique of the join of $s^{top}$
and a $|\Pi-\sum_{1}^{k}U_{i}|$-simplex $s^{bot}$ as the join of $s^{top}$ and
the opposite clique of $s^{bot}$ in the chromatic subdivision of
$|\Pi-\sum_{1}^{k}U_{i}|$-simplex. The carrier rule will be used to avoid
violating the task specification.

Lemma 5.7 can be used for the new input complexes: if an n-clique $\sigma$ has
an intersection with the protocol for some label $l_{n}$, then there exists an
opposite clique of this n-clique with this label. Suppose that an n-clique
$\sigma$ has some intersection vertices with some protocol with the label
$l_{n}$, denoted by $V_{int}$. By the induction hypothesis, it will have an
opposite clique with the label $l_{o}$. If the opposite clique with the label
$l_{o}$ of $\sigma$ is in the input complex for the label $l_{n}$, then we
will use it as the opposite clique of $\sigma$ with the label $l_{n}$.
Otherwise the opposite clique $\sigma^{{}^{\prime}}$ with the label $l_{o}$ is
in another input complex, then $\sigma^{{}^{\prime}}$ will also contain the
vertices set $V_{int}$. So, there exists an opposite clique of
$\sigma^{{}^{\prime}}$ with the label $l_{n}$. We will use the opposite clique
of $\sigma^{{}^{\prime}}$ with the label $l_{n}$ as the opposite clique of
$\sigma$ with the label $l_{n}$. There will be no conflict of output values.
If the vertex $v$ is shared by two n-cliques having an intersection with
$Input(l_{n})$, then the opposite cliques with the label $l_{o}$ will share
the vertex with the same process id. If the opposite cliques with the label
$(U,V)$ are both in or not in $Input(l_{n})$, the opposite cliques with the
label $l_{n}$ will share the vertex with the same process id. If only one of
the opposite cliques with the label $l_{o}$ denoted by $s^{oc}$ is in
$Input(s_{n})$, then the vertex $v$ will be at the intersection of two
subprotocols. The opposite clique of $s^{oc}$ with the label $l_{n}$ will not
change the intersection vertices, including the vertex $v$. Therefore, the
opposite cliques with the label $l_{o}$ will still share the vertex with the
same process id.

After phase $k$, the first $k$ process sets are determined which means the
adversary can limit itself to the subcomplex of $S^{t}$ reached from the input
complex labeled with
$[(U_{1},V_{1}),(U_{2},V_{2})\allowbreak...(U_{k},V_{k})]$. The adversary can
use the techniques in Section 5.2 to generate a restricted protocol.

###### Theorem 5.19.

For a general colorless task $(\mathcal{I},\mathcal{O},\Delta)$, there exists
an adversary that can finalize after the $k$-th phase and win against any
restricted extension-based prover if and only if there exists a protocol for
each $Input((U_{1},V_{1}),(U_{2},V_{2})\allowbreak...(U_{k},V_{k}))$ where
$\sum_{1}^{k}U_{i}\subseteq\Pi$ and all intersection simplices in the standard
chromatic subdivision of all initial configurations are compatible.

Now we will discuss the case of $\sum_{1}^{k}U_{i}=\Pi$. We will show that any
further division of the protocol will be unnecessary. Any further division
will still imply the existence of a protocol for
$Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})])$ since there must be a
protocol for the configurations reached from the schedule which repeats the
first partition $U_{1},U_{2},\allowbreak...U_{k}$ of $\Pi$. For example, if
the input complex $Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})])$ is
further divided into a sequence of input complexes
$Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k}),\allowbreak(U_{k+1},V_{k+1})])$
where $U_{k+1}$ is a subset of $\Pi$ and there exists a protocol for each such
input complex, then there is a protocol for the configurations reached from
the schedule which repeats the first partition twice. This protocol can be
used as a protocol for $Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})])$
without violating the carrier map. Note that this is not necessarily true for
those input complexes labeled by $[(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})]$
such that $\sum_{1}^{k}U_{i}\subsetneqq\Pi$. But this is not the reason why we
will not further subdivide the protocol since the existence of a protocol for
$Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})])$ is not enough for our
requirements: the intersection simplices have to be compatible. If we just use
the protocol for $Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})])$, the
output configurations of some shared simplices will change, just as the reason
why we will not use the standard form of restricted protocols.

Suppose that there is a set of subprotocols for some covering of
$Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})])$ where
$\sum_{1}^{k}U_{i}=\Pi$. What we will do is to construct a valid protocol for
$Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})])$ from these subprotocols.
A key observation is that for any intersection simplex of
$Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})])$ with other
$Input([(U_{1}^{{}^{\prime}},V_{1}^{{}^{\prime}}),\allowbreak...(U_{k}^{{}^{\prime}},\allowbreak
V_{k}^{{}^{\prime}})])$ where $\sum_{1}^{k}U_{i}^{{}^{\prime}}=\Pi$, it is
assumed to be compatible, and the most central simplex reached from it is
contained in only one subprotocol. This means that if we can connect these
subprotocols, i.e., have the intersection parts of different subprotocols
terminated with the same output configuration, we can generate a protocol that
satisfies the requirements of Theorem 5.19. We cannot do the same thing to
$Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})])$ where
$\sum_{1}^{k}U_{i}\subsetneqq\Pi$ since its intersection simplex with any
other input complex which is assumed to be compatible can be shared by more
than one subprotocol.

All processes must have seen the input values of the processes in $U_{1}$.
Therefore, we can use the most central simplex $s_{c}$ in the subdivision of
the simplex corresponding to the set of processes $U_{1}$ to connect the
subprotocols. For each intersection simplex $s_{i}$, it corresponds to a
process set $U_{k+1}$. We will construct a new subprotocol for
$Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k}),\allowbreak(U_{k+1},V_{k+1})])$
while keeping the output configuration of $s_{i}$ unchanged. There is a path
from some vertex $v_{i}$ of the output configuration of $s_{i}$ to some vertex
$v_{c}$ of the output configuration of $s_{c}$ using the original set of
subprotocols. First, we will terminate the intersection simplex $s_{i}$ with
its output configuration. Then we will terminate each vertex adjacent to the
terminated vertices with the value $v_{i}$. Finally, we will add layers
corresponding to the path from $v_{i}$ to $v_{c}$. The constructed protocol is
valid for $Input([(U_{1},V_{1})\allowbreak...(U_{k+1},V_{k+1})])$ and the
terminated values of intersection simplices with other subprotocols will all
be $v_{c}$. There always exists a path from $v_{i}$ to $v_{c}$ in which the
carrier of each vertex grows smaller since all common simplices between the
original subprotocols are compatible. And the carrier of $s_{i}$ is the
smallest compared to any other vertex in
$Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k}),\allowbreak(U_{k+1},V_{k+1})])$.
Therefore, using this path can avoid any task specification violation. Most
importantly, the terminated values of $s_{i}$ are not changed. We can choose
the same $v_{c}$ and build the protocol of
$Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k}),(U_{k+1},V_{k+1})])$ for
each process set $U_{k+1}$. These subprotocols can be united into a valid
protocol for $Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})])$. Therefore,
we have shown that it is not necessary to further divide the input complex
$Input([(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})])$.

Before giving the final result, we want to explain why the finalization after
the input complex is restricted to
$Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$ where
$\sum_{1}^{k}U_{i}=\Pi$ is sufficient for the adversary to win against any
extension-based prover. The prover cannot find a safety violation. To win
against the adversary, the only possible way is to construct infinite phases.
We assume $U_{i}\subseteq\Pi-\sum_{1}^{i-1}U_{l}$ for each $i$, but what if
the adversary chooses to terminate the phases, e.g., by having $U_{2}=U_{1}$?
Suppose that the prover ends the phase $i$ by extending the schedule by a
process set $U_{i}$, where $\sum U_{i}\subsetneqq\Pi$. By Lemma 5.12, the
processes in $\sum U_{i}$ will terminate with some output values after some
phase $k_{s}$. So $U_{k_{s}+1}$ contains some process in $\Pi-\sum U_{i}$. In
other words, there exists some phase $k_{e}$ where $\alpha(k_{e})$ contains
each process in $\Pi$. The restricted input complex after phase $k_{e}$ is
therefore contained in some $Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$
where $\sum_{1}^{k}U_{i}=\Pi$. The adversary can finalize after phase $k_{e}$
and win.

###### Theorem 5.20.

For a general colorless task$(\mathcal{I},\mathcal{O},\Delta)$, there exists
an adversary that can win against any restricted extension-based prover if and
only if there exists a protocol for each
$Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$ where
$\sum_{1}^{k}U_{i}=\Pi$ and all intersection simplices in the standard
chromatic subdivision of all initial configurations are compatible.

##  6\. Reductions of colorless tasks

In this section, we will present an application of our results in Section 5.
We can use Theorem 5.20 to discuss the reductions of colorless tasks in a
totally topological way. If a colorless task
$\mathcal{T}=(\mathcal{I},\mathcal{O},\Delta)$ reduces to another colorless
task
$\mathcal{S}=(\mathcal{I}^{{}^{\prime}},\mathcal{O}^{{}^{\prime}},\Delta^{{}^{\prime}})$,
then there exists a composition of protocols
$(\mathcal{P}_{2l},\mathcal{P}_{2l+1},\Xi_{2l+1})*\cdots*(\mathcal{P}_{0},\mathcal{P}_{1},\Xi_{1})$
that can solve the task $\mathcal{T}$. Each protocol
$(\mathcal{P}_{i-1},\mathcal{P}_{i},\Xi_{i})$, $1\leq i\leq 2l+1$ is an
immediate snapshot protocol or a protocol that solves the task $\mathcal{S}$.
So we will use the notation in Section 4 and denote the composed protocols as
$(B_{l+1}\cdot A_{l}\cdot B_{l}\cdot A_{l-1}\cdots A_{1}\cdot B_{1})$ where
each $A_{i}$ is the same protocol $A$ solving task $\mathcal{S}$ and each
$B_{i}$ is an IIS protocol. If task $\mathcal{S}$ has no extension-based
proofs, by Theorem 5.20 there exists a restricted protocol for each
$Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$ where
$\sum_{1}^{k}U_{i}=\Pi$ and all intersection simplices in the standard
chromatic subdivision of all initial configurations are compatible. In other
words, $A_{i}$ is not a valid protocol, but a sequence of subprotocols for
each $Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$. However, we will
still use the notation of the composed protocol and construct a protocol for
each such input complex of the task $\mathcal{T}$ from these subprotocols of
$\mathcal{S}$.

For each input configuration of $\mathcal{T}$ denoted by $C$, our goal is to
construct a sequence of subprotocols from each input complex
$Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$ in $\mathcal{I}$ to the
output complex of task $\mathcal{T}$. And these subprotocols shall satisfy the
compatibility condition. This is achieved by induction: for each
$Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$ we will subdivide
$Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$ and build a protocol from
each simplex of the subdivision to the output complex of some protocol in the
sequence. Each of such protocols is labeled with
$[(U_{1},V_{1}),\allowbreak...(U_{k},V_{k})]$. The first requirement is about
protocols with different labels. For each intersection simplex of the two
input complexes with labels $b_{1}$ and $b_{2}$, protocols with labels $b_{1}$
and $b_{2}$ containing the most central simplex will terminate it with the
same output configuration. Let $s_{c}$ denote the subsimplex of
$Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$ corresponding to $U_{1}$.
The second requirement is that the most central simplex of each intersection
simplex should be connected to the most central simplex of $s_{c}$ by a path
in which the carrier of each vertex becomes smaller. If the path goes through
two protocols with the same label, it will have a vertex in some shared output
configuration of two protocols.

First, we will construct a protocol from each input complex
$Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$ to the output complex of
$B_{1}$ by limiting the protocol $B_{1}$ to each input complex. No subdivision
of any $Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$ is needed here, and
therefore the second requirement is satisfied. Since all these protocols are
obtained from the same protocol $B_{1}$, any intersection simplex will be
mapped to the same complex in the output complex of $B_{1}$, and therefore is
compatible.

The induction procedures will be different depending on the next protocol. By
the induction hypothesis, for each $Input((U_{1},\allowbreak
V_{1}),\allowbreak...(U_{k},V_{k}))$, we have constructed a protocol from each
simplex $\sigma$ in the $n$-th iterated chromatic subdivision to the output
complex of the previous protocol. By the asynchronous computability theorem,
we know that there exists a color-preserving simplicial map from the $m$-th
iterated standard chromatic subdivision of $\sigma$ to the output complex of
the last protocol. We will choose $m$ to be the largest of any $\sigma$.

If the next protocol is some $B_{i}$ which is some IIS protocol. For each
$Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$, we will define a set of
protocols to the output complex of $B_{i}$ by composing the already
constructed protocols with $B_{i}$. Two requirements are satisfied since they
are satisfied when using the old set of protocols.

Otherwise the next protocol is some protocol $A_{i}$ which is in fact a
sequence of subprotocols of the task $\mathcal{S}$. For each simplex in the
$n$-th iterated standard chromatic subdivision of
$Input((U_{1},V_{1}),\allowbreak...(U_{k},\allowbreak V_{k}))$, the range of a
constructed protocol from it to the input complex of $A_{i}$ will be an
n-dimensional complex. We cannot compose this protocol with $A_{i}$ to obtain
the new protocol as we have done, since $A_{i}$ is not a real protocol at all.
So for each $Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$, we will
subdivide it $(n+m+1)$ times. For each simplex $\sigma$ in the $(n+m+1)$-th
iterated standard chromatic subdivision, we will define a protocol from
$\sigma$ to the input complex of $A_{i}$ by limiting some existing constructed
protocol denoted by $P_{c}$ to $\sigma$. Note that if two such protocols are
built from the same $P_{c}$, then any intersection simplex between them is
compatible. The range of each such protocol from $\sigma$ is in some
$Input((U_{1}^{{}^{\prime}},V_{1}^{{}^{\prime}}),\allowbreak...(U_{k}^{{}^{\prime}},V_{k}^{{}^{\prime}}))$
of task $\mathcal{S}$. Then we will compose this protocol with its
corresponding subprotocol of the task $\mathcal{S}$ to construct a new
protocol from $\sigma$ to the output complex of $A_{i}$. To prove the first
requirement, for each intersection simplex, consider the new protocol for the
$(n+m+1)$-th iterated standard chromatic subdivision of it. It will be mapped
to a complex in the output complex of $A_{i}$ in which the most central facet
will be shared by the newly constructed protocols with different labels.
Therefore the first requirement is satisfied.

By the induction hypothesis, the most central simplex of each intersection
simplex should be connected to the most central simplex of $s_{c}$ by a path
$v_{0},v_{1},....v_{l}$ in the $n$-th iterated standard chromatic subdivision
in which the carrier of each vertex is growing smaller. We will first link the
$v_{0}^{{}^{\prime}}$ of the most central simplex in the $(n+m+1)$-th iterated
standard chromatic subdivision to $v_{0}$. Using the same argument in the
proof of the first requirement, we know that any intersection simplex between
new protocols constructed from the same old protocol $P_{c}$ will be
compatible. Therefore the path from $v_{0}^{{}^{\prime}}$ to $v_{0}$ is
possible and the vertex on the boundary of two protocols is in the shared
output configuration. Readers can imagine a line from $v_{0}^{{}^{\prime}}$ to
$v_{0}$. Once it passes some boundary between protocols, it will choose to go
through the center of the boundary. The carrier of each vertex in this
deviation will be the same. For the same reason, a path can be constructed
from $v_{l}$ to $v_{l}^{{}^{\prime}}$. Now suppose that
$v_{0},v_{1},...v_{l^{{}^{\prime}}}$ where $l^{{}^{\prime}}<l$ is in the same
simplex of the $n$-th iterated standard chromatic subdivision. Again, we are
able to construct a carrier-shrinking path from $v_{0}$ to
$v_{l^{{}^{\prime}}}$ in which the vertex on the boundary of two protocols is
in the shared output configuration. The vertex $v_{l^{{}^{\prime}}}$ is in the
shared configuration $\tau$ of protocols for two simplices containing it in
$n$-th iterated standard chromatic subdivision, but may not be in the shared
configuration now since only some simplex $\tau^{{}^{\prime}}$ reached from
$\tau$ is shared now. We can construct a path from $v_{l^{{}^{\prime}}}$ to
$\tau^{{}^{\prime}}$ and then to $v_{l^{{}^{\prime}}}$ again. Note that the
carrier of each vertex in this path will be the same. Then we will use the
same techniques to each set of vertices
$v_{l^{{}^{\prime}}},...v_{l^{{}^{\prime\prime}}}$ in the same simplex of the
$n$-th iterated standard chromatic subdivision. The vertex $v_{l}$ is finally
reached and will join the path from $v_{l}$ to $v_{l}^{{}^{\prime}}$. So we
have constructed a carrier-shrinking path from $v_{0}^{{}^{\prime}}$ to
$v_{l}^{{}^{\prime}}$ and if it goes through two protocols, some vertex will
be in their shared configuration. Induction procedures are proved.

Finally, we will use the carrier-shrinking paths between intersection
simplices to construct a subprotocol from each
$Input((U_{1},V_{1}),\allowbreak...(U_{k},\allowbreak V_{k}))$ to the output
complex of task $\mathcal{T}$. Since we have proved that any division of a
protocol for $Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$ is
unnecessary, the techniques in the proof of Theorem 5.20 are used to generate
such a subprotocol. The intersection simplices of these subprotocols will be
compatible since the second requirement is maintained, and the merged
subprotocol will not change the output values of most central simplex of an
intersection simplex. Therefore, we have constructed a protocol for each input
complex $Input((U_{1},V_{1}),\allowbreak...(U_{k},V_{k}))$ of the task
$\mathcal{T}$ and any intersection simplex is compatible. By Theorem 5.20,
there is no extension-based proof for the task $\mathcal{T}$. Therefore, we
have proved the contrapositive of Theorem 4.1 for general colorless tasks.

##  7\. Conclusions

In this paper, we solve most of the open questions proposed in (BE, 21). We
have shown that if there is a reduction using multiple instances of
$\mathcal{S}$ from task $\mathcal{T}$ to $\mathcal{S}$ and there is no
augmented extension-based proof that no protocol can solve $\mathcal{S}$, then
there is no augmented extension-based proof that no protocol can solve
$\mathcal{T}$. Although most of the reductions used in research will not use
more than one instance, our result makes the choice of reduction easier. A
more important contribution is that we prove the topological properties for
colorless tasks to have no extension-based proofs. Previous work is related to
some specific tasks, such as the $(n,k)$-set agreement task, and this is the
first attempt for general tasks. We introduce a more general interaction
procedure for the prover and the adversary. We have also shown that assignment
queries will not give more power to the prover. Different versions of
extension-based proofs are equivalent in power for colorless tasks. Our
adversarial strategy does not require the condition that the task is colorless
before the finalization part in Section 5.2.4. An open problem that remains is
to extend our results to general tasks or to general tasks with the minimum
requirements. And we do believe that the concept of opposite cliques can be
used in future researches of extension-based proofs and perhaps other
questions of distributed computing.

###### Acknowledgements.

To Weidong Liu and Jiaxing Song for their discussions and support.

## References

  * AAE+ [19] Dan Alistarh, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu.  Why extension-based proofs fail.  Proceedings of the 51’st Annual ACM Symposium on Theory of Computing (STOC), page 986–996, 2019.
  * AC [11] Hagit Attiya and Armando Castañeda.  A non-topological proof for the impossibility of k-set agreement.  In Xavier Défago, Franck Petit, and Vincent Villain, editors, Stabilization, Safety, and Security of Distributed Systems, pages 108–119, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
  * AP [12] Hagit Attiya and Ami Paz.  Counting-based impossibility proofs for renaming and set agreement.  In Proceedings of the 26th International Conference on Distributed Computing, DISC’12, page 356–370, Berlin, Heidelberg, 2012. Springer-Verlag.
  * BE [21] Kayman Brusse and Faith Ellen.  Reductions and extension-based proofs.  In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC’21, page 497–507, New York, NY, USA, 2021. Association for Computing Machinery.
  * [5] Elizabeth Borowsky and Eli Gafni.  Generalized flp impossibility result for t-resilient asynchronous computations.  In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’93, page 91–100, New York, NY, USA, 1993. Association for Computing Machinery.
  * [6] Elizabeth Borowsky and Eli Gafni.  Immediate atomic snapshots and fast renaming.  In Proceedings of the Twelfth Annual ACM Symposium on Principles of Distributed Computing, PODC ’93, page 41–51, New York, NY, USA, 1993. Association for Computing Machinery.
  * BG [97] Elizabeth Borowsky and Eli Gafni.  A simple algorithmically reasoned characterization of wait-free computation (extended abstract).  In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’97, page 189–198, New York, NY, USA, 1997. Association for Computing Machinery.
  * BMZ [88] Ofer Biran, Shlomo Moran, and Shmuel Zaks.  A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor.  In Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC ’88, page 263–275, New York, NY, USA, 1988. Association for Computing Machinery.
  * Cha [93] Soma Chaudhuri.  More choices allow more faults: Set consensus problems in totally asynchronous systems.  Inf. Comput., 105(1):132–158, jul 1993.
  * CR [08] Armando Castaneda and Sergio Rajsbaum.  New combinatorial topology upper and lower bounds for renaming.  In Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, PODC ’08, page 295–304, New York, NY, USA, 2008. Association for Computing Machinery.
  * FLP [85] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson.  Impossibility of distributed consensus with one faulty process.  J. ACM, 32(2):374–382, apr 1985.
  * GMRT [09] Eli Gafni, Achour Mostéfaoui, Michel Raynal, and Corentin Travers.  From adaptive renaming to set agreement.  Theor. Comput. Sci., 410(14):1328–1335, mar 2009.
  * GRH [06] Eli Gafni, Sergio Rajsbaum, and Maurice Herlihy.  Subconsensus tasks: Renaming is weaker than set agreement.  In Proceedings of the 20th International Conference on Distributed Computing, DISC’06, page 329–338, Berlin, Heidelberg, 2006. Springer-Verlag.
  * HKR [13] Maurice Herlihy, Dmitry N. Kozlov, and Sergio Rajsbaum.  Distributed Computing Through Combinatorial Topology.  Morgan Kaufmann, 1st. edition, 2013.
  * HS [97] Gunnar Hoest and Nir Shavit.  Towards a topological characterization of asynchronous complexity.  In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, PODC ’97, page 199–208, New York, NY, USA, 1997. Association for Computing Machinery.
  * HS [99] Maurice Herlihy and Nir Shavit.  The topological structure of asynchronous computability.  J. ACM, 46(6):858–923, nov 1999.
  * MRT [06] Achour Mostefaoui, Michel Raynal, and Corentin Travers.  Exploring gafni’s reduction land: From $\omega^{k}$ wait-free adaptive ($(2p-\lceil\frac{p}{n}\rceil)$)-renaming via k-set agreement.  In Proceedings of the 20th International Conference on Distributed Computing, DISC’06, page 1–15, Berlin, Heidelberg, 2006. Springer-Verlag.
  * Spa [66] Edwin H. Spanier.  Algebraic Topology.  Springer-Verlag, New York, 1966.
  * SZ [00] Michael Saks and Fotios Zaharoglou.  Wait-free k-set agreement is impossible: The topology of public knowledge.  SIAM J. Comput., 29(5):1449–1483, mar 2000.