# A Speedup Theorem for Asynchronous Computation with Applications to
Consensus and Approximate Agreement

Pierre Fraigniaud<EMAIL_ADDRESS>IRIF, CNRS and Université Paris
CitéParisFrance ,  Ami Paz<EMAIL_ADDRESS>LISN, CNRS and Université Paris
SaclayParisFrance and  Sergio Rajsbaum<EMAIL_ADDRESS>Instituto de
Matemáticas, UNAMMexico CityMexico

###### Abstract.

We study two fundamental problems of distributed computing, _consensus_ and
_approximate agreement_ , through a novel approach for proving lower bounds
and impossibility results, that we call the _asynchronous speedup theorem_.
For a given $n$-process task $\Pi$ and a given computational model $M$, we
define a new task, called the _closure_ of $\Pi$ with respect to $M$. The
asynchronous speedup theorem states that if a task $\Pi$ is solvable in $t\geq
1$ rounds in $M$, then its closure w.r.t. $M$ is solvable in $t-1$ rounds in
$M$. We prove this theorem for iterated models, as long as the model allows
solo executions. We illustrate the power of our asynchronous speedup theorem
by providing a new proof of the wait-free impossibility of consensus using
read/write registers, and a new proof of the wait-free impossibility of
solving consensus using registers and test&set objects for $n>2$. The proof is
merely by showing that, in each case, the closure of consensus (w.r.t. the
corresponding model) is consensus itself. Our main application is the study of
the power of additional objects, namely test&set and binary consensus, for
wait-free solving approximate agreement _faster_. By analyzing the closure of
approximate agreement w.r.t. each of the two models, we show that while these
objects are more powerful than read/write registers from the computability
perspective, they are not more powerful as far as helping solving approximate
agreement faster is concerned.

Pierre Fraigniaud received support from the ANR project DUCAT.

Part of this work was done while Sergio Rajsbaum was visiting LIX at École
Polytechnique, and IRIF at Université Paris Cité, France. He received
additional support from UNAM-PAPIIT IN106520

##  1\. Introduction

One of the goals of the theory of distributed computing is to understand what
can be achieved by a given distributed system. A great deal of research has
been devoted to develop techniques for showing that certain problems cannot be
solved, or to prove lower bounds on the resources needed to solve some given
problem (Attiya and Ellen, 2014; Fich and Ruppert, 2003; Lynch, 1989). Much of
this research is motivated by the need to understand the solvability of
_consensus_ and _approximate agreement_ , two of the central tasks of
distributed computing. In particular, this line of research lead to the
introduction of bivalency (Fischer et al., 1985) and indistinguishability
(Attiya and Rajsbaum, 2020) arguments, and later on to the discovery of the
close connection between distributed computing and algebraic topology, based
on the study of topological invariants of the protocol complex representing a
given model of computation (Herlihy et al., 2013). In this paper we propose a
new approach to prove unsolvability results and time lower bounds.

###  1.1. Asynchronous Speedup Theorem

We introduce the _asynchronous speedup theorem_ for shared-memory computing,
inspired by the recent speedup technique (Balliu et al., 2019; Brandt, 2019)
for the LOCAL model of synchronous failure-free distributed computing in
networks. Specifically, we consider the iterated shared-memory model, where
the memory is organized in arrays $M_{r}$, $r\geq 1$, of $n$ single-
writer/multiple-readers (SWMR) registers (one per process), and each round $r$
of the protocol is executed on the array $M_{r}$. Recall that a task
$\Pi=(\mathcal{I},\mathcal{O},\Delta)$ is defined by a collection
$\mathcal{I}$ of possible input configurations, a collection $\mathcal{O}$ of
possible output configurations, and a map $\Delta:\mathcal{I}\to
2^{\mathcal{O}}$ specifying an input-output relation. A subset of processes
starting with inputs as specified by a configuration $\sigma\in\mathcal{I}$
must output values that define a configuration $\tau\in\Delta(\sigma)$.

For our speedup theorem, we define the _closure_ of a task $\Pi$ with respect
to a computational model $M$, denoted $\mbox{\footnotesize\sf
CL}_{M}(\Pi)=(\mathcal{I},\mathcal{O}^{\prime},\Delta^{\prime})$, which is
supposed to be a slightly easier version of $\Pi$ under $M$. Recall that an
algorithm solves a task $\Pi$ in $t$ rounds if, whenever a subset of processes
start with inputs as specified by a configuration $\sigma\in\mathcal{I}$,
after executing $t$ rounds, they must output values that define a
configuration $\tau\in\Delta(\sigma)$. Our asynchronous speedup theorem states
that, for every $t\geq 1$, if a task $\Pi$ is solvable in $t$ rounds in $M$,
then $\mbox{\footnotesize\sf CL}_{M}(\Pi)$ is solvable in $t-1$ rounds in $M$.
Therefore, to establish a lower bound on the number $t$ of rounds for solving
$\Pi$, it suffice to show that iterating the closure operation for $t$ times
starting with $\Pi$, results in a task that is not solvable in zero rounds.
Alternately, impossibility results follow when the closure operator can be
performed infinitely many times without ever reaching a task solvable in zero
rounds, which is typically the case when the closure of a task is the task
itself.

Notice that the notion of “$\mbox{\footnotesize\sf CL}_{M}(\Pi)$ being easier
to solve than $\Pi$” is with respect to the model $M$ of computation. We
consider models obtained by extending the standard shared-memory model with
objects more powerful than SWMR registers—the task $\mbox{\footnotesize\sf
CL}_{M}(\Pi)$ then depends on the nature of these objects. Intuitively,
$\mbox{\footnotesize\sf CL}_{M}(\Pi)$ is supposed to be easier than $\Pi$
because it allows, on each given input configuration $\sigma\in\mathcal{I}$ to
output some values that are illegal according to $\Delta$. To prevent
$\mbox{\footnotesize\sf CL}_{M}(\Pi)$ from being _too_ easy in $M$, it is
however required that such an output configuration $\tau$ is “close to a legal
solution”, in the following sense: there must exists a $1$-round algorithm
which, starting with the configuration $\tau$ as input, computes legal outputs
for $\sigma$, that is, outputs a configuration in $\Delta(\sigma)$. If there
is such a $1$-round algorithm for $M$, then the configuration $\tau$ is added
to the collection $\Delta^{\prime}(\sigma)$ of legal output configurations for
$\sigma$ in the closure task $\mbox{\footnotesize\sf CL}_{M}(\sigma)$.

###  1.2. Our Results

We present our asynchronous speedup theorem for any iterated asynchronous
model with SWMR registers, as long as this model allows _solo_ executions
(Theorem 3). Such models include the usual wait-free iterated immediate
snapshot (IIS), iterated snapshot, and iterated collect models. They also
include _affine models_ (Kuznetsov et al., 2018) that allow solo executions,
such as the $k$-concurrency model (Gafni and Guerraoui, 2011). Roughly, an
affine model is obtained from the IIS model by removing some executions.
Iterated models with solo executions that _add_ some executions have also been
studied, such as the $d$-solo models (Herlihy et al., 2017), where $d$
processes may run solo in the same execution. Note that lower bounds for
iterated models, as the ones we prove here, immediately apply to the non-
iterated variants of the same models—in a non-iterated model, the adversary
can still choose to have only executions where all processes finish their
$r$-th step before taking their $(r+1)$-th step.

We illustrate the use of our asynchronous speedup theorem by revisiting the
renowned wait-free impossibility of solving consensus. We show how to derive
this impossibility result in a simple way from our speedup theorem (Corollary
5): to prove the impossibility of consensus, it is enough to establish that
the closure of consensus is consensus itself. Next, we present an extension of
our speedup theorem for models as above augmented with objects more powerful
than SWMR registers (Theorem 1). We illustrate its usefulness with a new proof
of the impossibility for consensus among $n\geq 3$ processes when the
processes have access to a test&set object at each round (Corollary 2).

After considering solvability, we move our attention to the question of how
much objects in Herlihy’s consensus hierarchy can help solving a problem
_faster_. We present two examples of objects that are more powerful than
read/write registers, namely test&set and binary consensus, and yet not more
powerful as far as helping solving approximate agreement faster is concerned.
Our proofs, based on our asynchronous speedup theorem, provide novel
information about the topology of such extended models. More specifically, in
the second part of the paper, we illustrate the power of the asynchronous
speedup theorem by establishing new lower bounds for $\epsilon$-approximate
agreement, in the wait-free IIS model with access to test&set or binary
consensus objects. We first show that the number of rounds required for
solving $\epsilon$-approximate agreement in the wait-free IIS model among
$n\geq 3$ processes is at least $\lceil\log_{2}(1/\epsilon)\rceil$ (Corollary
3), which is tight, and then we show that augmenting the model with test&set
objects does not reduce the time complexity at all (Theorem 4), assuming that
each of the processes calls all the test&set objects. These results are
obtained by simply showing that the closure of $\epsilon$-approximate
agreement in the considered model is the $(2\epsilon)$-approximate agreement
task. For $n=2$, $\epsilon$-approximate agreement can be solved in a single
round in the wait-free IIS model with test&set, while in the wait-free IIS
model without additional objects we show that $\epsilon$-approximate agreement
among $n=2$ processes requires $\lceil\log_{3}1/\epsilon\rceil$ rounds
(Corollary 3). This bound is proved by showing that the closure of
$\epsilon$-approximate agreement in this case is the $(3\epsilon)$-approximate
agreement task, and is also known to be tight.

Finally, we show that the number of rounds required by $n\geq 3$ processes for
solving the $\epsilon$-approximate agreement task in the wait-free IIS model
augmented with a binary consensus object is at least
$\min\\{\lceil\log_{2}1/\epsilon\rceil,\lceil\log_{2}n\rceil-1\\}$ (Theorem
5), when we assume that each input to the binary consensus object depends
solely on the process ID and of the round number. In this context, the closure
of $\epsilon$-approximate agreement is not necessarily
$(2\epsilon)$-approximate agreement. However, we can show that, for a set of
at least half of the processes, the closure of $\epsilon$-approximate
agreement when only the processes in this set participate is
$(2\epsilon)$-approximate agreement. By iterating this argument, we get that
if there is a $t$-round algorithm for solving $\epsilon$-approximate agreement
among $n$ processes, then there is a $t-r$ round algorithm for solving
$(2^{r}\epsilon)$-approximate agreement among $n/2^{r}$ processes. We lose an
additive factor $-1$ for technical reasons related to the fact that
$\epsilon$-approximate agreement is solvable when there are only $n=2$
processes. Note that our lower bound is essentially tight as there exists an
algorithm for solving $\epsilon$-approximate agreement in
$\lceil\log_{2}1/\epsilon\rceil$ rounds in the wait-free IIS model (Aspnes and
Herlihy, 1990), and there exists an algorithm for solving multi-value
consensus in $\lceil\log_{2}n\rceil$ rounds (Mostefaoui et al., 2000; Raynal,
2018) in the wait-free IIS model with binary consensus objects.

###  1.3. Related Work

The computability and complexity of fault-prone, asynchronous consensus and
approximate agreement is a well studied topic. Fischer, Lynch, and Paterson
(FLP) (Fischer et al., 1985) showed that consensus cannot be solved in a
message passing system even if only one process may fail by halting. Later,
Herlihy (Herlihy, 1991) studied wait-free computation in the shared-memory
model, and proved the consensus impossibility in this model. Motivated by the
need to analyze problems other than consensus, Herlihy and Shavit (Herlihy and
Shavit, 1999) introduced the use of combinatorial topology for reasoning about
computations in asynchronous, wait-free distributed systems, in which any
number of processes may crash. They proved the asynchronous computability
theorem, which states a topological condition that is necessary and sufficient
for a task to be wait-free solvable using read/write registers. Approaches
similar to the one of Herlihy and Shavit were presented in the same time by
Saks and Zaharoglou (Saks and Zaharoglou, 1993) and by Borowsky and Gafni
(Borowsky and Gafni, 1993), but the formalization of Herlihy and Shavit is the
one commonly used today. To conclude, the two techniques that have been
extensively used for proving impossibility results for consensus and
approximate agreement are based on either valency (Fischer et al., 1985) or
connectivity analysis (Herlihy and Shavit, 1999), in addition to indirect,
reduction (Herlihy, 1991) or simulation techniques e.g. (Chandra et al.,
2005). Our technique of computing the closure of consensus provides a novel
way for proving such impossibility results. Regarding complexity issues, Hoest
and Shavit (Hoest and Shavit, 2006) showed how the topological approach can
also be used for deriving time lower bounds for wait-free algorithms in the
IIS model, as we do. Attiya, Castañeda, Herlihy and Paz (Attiya et al., 2019)
used similar techniques for proving time upper bounds, and Ellen, Gelashvili,
and Zhu (Ellen et al., 2018) used them for proving space lower bounds. One aim
of our paper is to investigate further the use of combinatorial topology in
the context of asynchronous computing.

Soon after the celebrated FLP consensus impossibility result, Dolev, Lynch,
Pinter, Stark, and Weihl (Dolev et al., 1986) introduced the approximate
agreement task, in which each process has a real valued input, and processes
must agree on output values within the range of inputs, that are at most
$\epsilon$ apart. Aspnes and Herlihy (Aspnes and Herlihy, 1990) proved a lower
bound of $\lceil\log_{3}1/\epsilon\rceil$ rounds and an upper bound of
$\lceil\log_{2}1/\epsilon\rceil$ rounds in the wait-free SWMR model, a gap
that was later closed by Hoest and Shavit (Hoest and Shavit, 2006), who proved
a tight bound on the number of rounds needed to solve approximate agreement:
$\lceil\log_{3}1/\epsilon\rceil$ for $n=2$, and
$\lceil\log_{2}1/\epsilon\rceil$ for $n\geq 3$. A similar result was recently
proved in the context of dynamic networks by Függer, Nowak and Schwarz (Függer
et al., 2021), where the reader can find a thorough discussion about the
literature studying approximate agreement, and about the importance of this
problem w.r.t. applications. Hoest and Shavit (Hoest and Shavit, 2006) prove
their lower bounds using a global analysis of the protocol complex, while
Függer, Nowak and Schwarz (Függer et al., 2021) extend the notion of valency
used for consensus (Fischer et al., 1985; Moses and Rajsbaum, 2002) for
proving their results. We establish these lower bounds in a novel way, by
computing the closure of the approximate agreement task.

In addition to proving the wait-free consensus impossibility, Herlihy
(Herlihy, 1991) also derived a hierarchy of objects such that no object at one
level has a wait-free implementation in terms of objects at lower levels,
introducing a remarkable technique of reduction to a consensus protocol. There
is plenty of work on extending the wait-free IIS model with more powerful
objects, but only from the computability perspective, e.g. (Gafni and
Rajsbaum, 2010; Imbs et al., 2015) using simulations, or using topology e.g.
(Herlihy and Rajsbaum, 1995). We are not aware of any use of this technique
for complexity results, to study as we do, using strong objects to solve
approximate agreement faster.

Last, but not least, a goal of this research is to understand the potential
extension of the recent speedup technique (Balliu et al., 2019; Brandt, 2019)
from the (synchronous failure-free) LOCAL model to asynchronous models with
crash-prone processes. In the LOCAL model, the uncertainly about how a
hypothetical protocol would solve a problem in one round, comes from unknown
inputs of far away processes. In contrast, in the asynchronous setting, the
uncertainty is of a very different nature, about what other processes have
read. There have been few recent attempts to approach distributed network
computing through the lens of algebraic topology (Castañeda et al., 2021;
Fraigniaud and Paz, 2020). An extension of the speedup technique in (Balliu et
al., 2019; Brandt, 2019) to arbitrary round-based full-information models has
been proposed in (Bastide and Fraigniaud, 2021). This extension applies to
wait-free shared-memory computing in particular, but only for $2$ processes.
Our approach applies to an arbitrarily large number of processes.

##  2\. Model

We consider the standard _read-write shared memory_ distributed computing
model (Attiya and Welch, 2004), and we adopt a standard framework for modeling
distributed computation, by using concepts borrowed from algebraic topology
(Herlihy et al., 2013). The reader unfamiliar with these notions is referred
to Appendix A for more details.

###  2.1. Iterated Models

We consider distributed systems with $n\geq 2$ asynchronous processes, labeled
by distinct integers from 1 to $n$. Every process $i$ initially knows its
identity $i$ as well as the total number $n$ of processes in the system. We
focus on generic round-based algorithms of the following form. All read and
write operations are atomic. Specifically, Algorithm 1 is for the _iterated_
model, in which the shared-memory is organized in arrays $M_{r}$, $r\geq 1$,
of $n$ single-writer/multiple-readers registers (one per process), and each
round $r$ of the protocol is executed on the array $M_{r}$. At each round,
each process $i$ updates its so-called _view_ $V_{i}$ by collecting the views
of the other processes. To this end, it uses a _collect_ operation, which
consists of reading all registers $M_{r}[1..n]$ sequentially, in arbitrary
order. The initial view of a process is its input, and, after $t$ rounds or
write-collect, each process outputs a value which depends of its view after
$t$ rounds, i.e., of all the information accumulated by the process during the
execution of the algorithm.

1 $V_{i}\leftarrow x_{i}$

2   __ for $r=1$ to $t$

3 $\mathbf{write}\;(i,V_{i})$ in register $M_{r}[i]$

4 $V_{i}\leftarrow\mathbf{collect}\;M_{r}[1..n]$

5 end

6$y_{i}\leftarrow f(i,V_{i})$

output $y_{i}$.

Algorithm 1 Code for process $i\in[n]$ with input $x_{i}$

Two classical stronger variants of the collect instruction are considered in
this paper. _Snapshot_ corresponds to the scenario in which the collect
operation itself is atomic, that is, all registers $M_{r}[1..n]$ are globally
read simultaneously at once, in an atomic manner (Attiya and Welch, 2004).
_Immediate snapshot_ (Borowsky and Gafni, 1993; Saks and Zaharoglou, 1993)
corresponds to the scenario in which each write-snapshot sequence of
operations is itself atomic, that is, not only all registers are read
simultaneously at once, but the snapshot occurs “immediately” after the write
operation: a set of processes first all perform a write operation, and
immediately after they all perform an atomic snapshot (the order of reads
inside the set of processes is not important, and so is the order of snapshot
operations). Our lower bound technique applies to the three wait-free models
with write-collect, write-snapshot, or immediate snapshot, and we shall
establish our lower bound for approximate agreement using the stronger model,
i.e., iterated immediate snapshot, or IIS for short.

###  2.2. Task Solvability

A _task_ for $n$ processes is a triple $\Pi=(\mathcal{I},\mathcal{O},\Delta)$
where $\mathcal{I}$ and $\mathcal{O}$ are $(n-1)$-dimensional complexes,
respectively called _input_ and _output_ complexes, and $\Delta:\mathcal{I}\to
2^{\mathcal{O}}$ is an input-output specification. Every simplex
$\sigma=\\{(i,x_{i}):i\in I\\}$ of $\mathcal{I}$, where
$I=\mbox{\sc{id}}(\sigma)$ is a non-empty subset of $[n]$, defines a legal
input state corresponding to the scenario in which, for every $i\in I$,
process $i$ starts with input value $x_{i}$. Similarly, every simplex
$\tau={\\{(i,y_{i}):i\in I\\}}$ of $\mathcal{O}$ defines a legal output state
corresponding to the scenario in which, for every $i\in I$, process $i$
outputs the value $y_{i}$. The map $\Delta$ is an input-output relation
specifying, for every input state $\sigma\in\mathcal{I}$, the set of output
states $\tau\in\mathcal{O}$ with $\mbox{\sc{id}}(\tau)=\mbox{\sc{id}}(\sigma)$
that are legal with respect to $\sigma$. That is, assuming that only the
processes in $\mbox{\sc{id}}(\sigma)$ participate to the computation (the set
of participating processes is not known a priori to the processes in
$\sigma$), these processes are allowed to output any simplex
$\tau\in\Delta(\sigma)$. $\Delta(\sigma)$ can be viewed as a collection of
simplexes, each with the same set of IDs as $\sigma$, or, alternatively, as
the complex induced by this set of simplexes. It is often assumed that
$\Delta$ is a _carrier_ map (that is, for every
$\sigma,\sigma^{\prime}\in\mathcal{I}$, if $\sigma^{\prime}\subseteq\sigma$
then $\Delta(\sigma^{\prime})\subseteq\Delta(\sigma)$ as subcomplexes), but in
this paper we do not enforce this requirement into the definition of tasks.

Given a simplex $\sigma=\\{(i,x_{i}):i\in I\\}\in\mathcal{I}$ for some
$I=\mbox{\sc{id}}(\sigma)\subseteq[n]$, one round of communication performed
by the processes in $\mbox{\sc{id}}(\sigma)$ as in Algorithm 1 results in
various possible simplices, depending on the interleaving of the different
write and read operations. Such a simplex is of the form
$\tau=\\{(i,V_{i}):i\in I\\}$, where $V_{i}=\\{(j,x_{j}):j\in J_{i}\\}$ is the
_view_ of process $i$ after one round. This view, or equivalently, the set
$J_{i}\subseteq I$, depends on the communication model $M$, i.e., write-
collect, write-snapshot, or immediate snapshot. These simplices induces a
complex, denoted by $\mathcal{P}^{(1)}(\sigma)$, whose structure differs
according to the three models considered on this paper. Figure 8 in Appendix B
displays an example of these three different complexes, for a 2-dimensional
simplex $\sigma$ (i.e., a system with three processes). In the case of
immediate snapshot, $\mathcal{P}^{(1)}(\sigma)$ is the complex obtained by
performing a chromatic subdivision of $\sigma$ (Herlihy and Shavit, 1999).
That is, $\tau=\\{(i,V_{i}):i\in I\\}$ is in $\mathcal{P}^{(1)}(\sigma)$ if
and only if, for every $i,j\in I$, $j\in V_{i}$ or $i\in V_{j}$, and if $j\in
V_{i}$ then $V_{j}\subseteq V_{i}$. We denote by $\Xi$ the map transforming
every $\sigma\in\mathcal{I}$ into $\mathcal{P}^{(1)}(\sigma)$, and by
$\mathcal{P}^{(1)}=\cup_{\sigma\in\mathcal{I}}\mathcal{P}^{(1)}(\sigma)$. The
map $\Xi$ depends on the communication model $M$.

The topological transformation from $\sigma$ to $\mathcal{P}^{(1)}(\sigma)$
can be iterated, yielding the sequence $(\mathcal{P}^{(t)})_{t\geq 0}$ where,
for every simplex ${\sigma\in\mathcal{I}}$,
$\mathcal{P}^{(0)}(\sigma)=\sigma$, and, for every $t\geq 1$,
$\mathcal{P}^{(t)}(\sigma)=\Xi(\mathcal{P}^{(t-1)}(\sigma))$. For every input
complex $\mathcal{I}$, and every $t\geq 0$, the complex $\mathcal{P}^{(t)}$ is
called the _protocol complex_ after $t$ rounds. This complex is the union, for
all simplices $\sigma\in\mathcal{I}$ of the complex
$\mathcal{P}^{(t)}(\sigma)$ resulting from $t$ rounds starting from input
$\sigma$. Note that for any two input simplices $\sigma=\\{(i,x_{i}):i\in
I\\}$ and $\sigma^{\prime}=\\{(i,x^{\prime}_{i}):i\in I\\}$, the complexes
$\mathcal{P}^{(1)}(\sigma)$ and $\mathcal{P}^{(1)}(\sigma^{\prime})$ are
isomorphic. We denote by

(1) $\chi:\mathcal{P}^{(1)}(\sigma)\to\mathcal{P}^{(1)}(\sigma^{\prime})$

the canonical isomorphism that maps every vertex $v=(i,\\{(j,x_{j}):j\in
J_{i}\\})$ of $\mathcal{P}^{(1)}(\sigma)$ to the vertex
$\chi(v)={(i,\\{(j,x^{\prime}_{j}):j\in J_{i}\\})}$ of
$\mathcal{P}^{(1)}(\sigma^{\prime})$. Finally, recall that a task
$\Pi=(\mathcal{I},\mathcal{O},\Delta)$ is solvable in $t$ rounds if and only
if there exists a simplicial map $f:\mathcal{P}^{(t)}\to\mathcal{O}$ from the
$t$-round protocol complex to the output complex that agrees with $\Delta$,
i.e., for every $\sigma\in\mathcal{I}$,
$f(\mathcal{P}^{(t)}(\sigma))\subseteq\Delta(\sigma).$ The mapping $f$ is
defined by the vertices, i.e., for $\sigma=\\{(i,V_{i}):i\in I\\}$ we have
$f(\sigma)=\\{f(i,V_{i}):i\in I\\}$. The simplicial map $f$ is merely the
function $f$ used in Algorithm 1 for computing the output values of the
processes.

##  3\. Closure and Speedup Theorem

This section describes our main tool for deriving lower bounds and
impossibility results, namely an _asynchronous speedup theorem_. This theorem
is based on a notion of _closure_ defined hereafter.

###  3.1. A Closure of a Task

In this section, we define the notion of a _closure task_ (Figure 2). As it
will be shown later, given a computational model $M$, and given a task $\Pi$,
the closure of $\Pi$ w.r.t. $M$, denoted by $\mbox{\footnotesize\sf
CL}_{M}(\Pi)$, is a simpler task in the sense that if $\Pi$ is solvable in $t$
rounds in model $M$, then $\mbox{\footnotesize\sf CL}_{M}(\Pi)$ is solvable in
$t-1$ rounds in model $M$. In order to define the closure of a task, we first
define another task, called _local task_ (Figure 1), which does not depend on
$M$, but only on $\Pi$. Intuitively, this task closes the one-round gap
between the round-complexities of $\mbox{\footnotesize\sf CL}_{M}(\Pi)$ and
$\Pi$ by taking the outputs of $\mbox{\footnotesize\sf CL}_{M}(\Pi)$ as input,
and producing legal outputs for $\Pi$.

Let $\Pi=(\mathcal{I},\mathcal{O},\Delta)$ be a task. We say that a set
$\tau\subseteq V(\mathcal{O})$ of output vertices is _chromatic_ if, for any
two vertices $v$ and $v^{\prime}$ of $\tau$,
$\mbox{\sc{id}}(v)\neq\mbox{\sc{id}}(v^{\prime})$. Intuitively, to every
simplex $\sigma\in\mathcal{I}$, and to every chromatic set of output vertices
$\tau\subseteq V(\mathcal{O})$ satisfying
$\mbox{\sc{id}}(\tau)=\mbox{\sc{id}}(\sigma)$, we associate a specific task
with input $\tau$, viewed as a complex, and whose objective is to construct a
legal solution in $\Delta(\sigma)$. Note that $\tau$ is a chromatic set of
vertices in $V(\mathcal{O})$, but is not necessarily a simplex in
$\mathcal{O}$. Given a chromatic complex $\mathcal{K}$ with vertex IDs in
$[n]$, and given a non-empty set $I\subseteq[n]$, we denote by
$\mathsf{proj}_{I}(\mathcal{K})$ the subcomplex of $\mathcal{K}$ induced by
the vertices with IDs in $I$.

Figure 1. Local task

###### Definition 0.

Given a task $\Pi=(\mathcal{I},\mathcal{O},\Delta)$, a simplex
$\sigma\in\mathcal{I}$, and a chromatic set $\tau\subseteq V(\Delta(\sigma))$
satisfying $\mbox{\sc{id}}(\tau)=\mbox{\sc{id}}(\sigma)$, the _local task for
$\sigma$ and $\tau$_ is the task
$\Pi_{\tau,\sigma}=(\tau,\Delta(\sigma),{\Delta}_{\tau,\sigma})$ where
${\Delta}_{\tau,\sigma}:\tau\to 2^{\Delta(\sigma)}$ is the map defined by:

  1. (1)

for every vertex $v\in\tau$: ${\Delta}_{\tau,\sigma}(v)=\\{v\\}$;

  2. (2)

for every $\tau^{\prime}\subseteq\tau$ with $|\tau^{\prime}|>1$:
${\Delta}_{\tau,\sigma}(\tau^{\prime})=\mathsf{proj}_{\mbox{\footnotesize$\mbox{\sc{id}}$}(\tau^{\prime})}\big{(}\Delta(\sigma)\big{)}.$

Figure 1 provides an illustration of a local task, and in particular of the
map ${\Delta}_{\tau,\sigma}$. This map seems similar to $\Delta$ restricted to
$\sigma$, but there are several differences that should be noted. First, while
$\Delta$ takes as inputs simplices of the _input complex_ $\mathcal{I}$, the
map ${\Delta}_{\tau,\sigma}$ takes as inputs subsets of $\tau$, which are sets
of vertices in the _output complex_ $\mathcal{O}$; both maps return sets of
simplices of the output complex $\mathcal{O}$. Second,
${\Delta}_{\tau,\sigma}$ is more restrictive than $\Delta$ for solo
executions, as the vertices of $\tau$ are fixed by ${\Delta}_{\tau,\sigma}$ —
a process $i$ of $\tau$ running solo must output its value $y_{i}$ in $\tau$.
And third, ${\Delta}_{\tau,\sigma}$ is more liberal than $\Delta$ in the other
executions, as for a face $\tau^{\prime}$ of $\tau$ with dimension greater
than $0$, the image of $\tau^{\prime}$ by ${\Delta}_{\tau,\sigma}$ is any
simplex of $\Delta(\sigma)$ colored with the IDs of the processes in
$\tau^{\prime}$.

##### Remark.

Given the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta(\sigma),{\Delta}_{\tau,\sigma})$ and
$\tau^{\prime}\subseteq\tau$, the set ${\Delta}_{\tau,\sigma}(\tau^{\prime})$
induces a subcomplex of $\Delta(\sigma)$, potentially reduced to a single
vertex whenever $|\tau^{\prime}|=1$. In particular, if $\tau$ is not a single
vertex then ${\Delta}_{\tau,\sigma}(\tau)=\Delta(\sigma)$.

We are now ready to define the closure task $\mbox{\footnotesize\sf
CL}_{M}(\Pi)$, which will be a task that is expected to be easier than $\Pi$
for model $M$. Given an input simplex $\sigma$ for $\Pi$, the closure of $\Pi$
allows to output chromatic sets of vertices $\tau\subseteq V(\Delta(\sigma))$
which are not simplices of $\Delta(\sigma)$. However, this set $\tau$ must be
“close to each other” in $\Delta(\sigma)$, in the sense that the local task
$\Pi_{\tau,\sigma}$ can be solved in one round w.r.t. a given model $M$.

###### Definition 0.

The _closure_ of a task $\Pi=(\mathcal{I},\mathcal{O},\Delta)$ with respect to
a communication model $M$ is the task $\mbox{\footnotesize\sf
CL}_{M}(\Pi)=(\mathcal{I},\mathcal{O}^{\prime},\Delta^{\prime})$ where
$V(\mathcal{O}^{\prime})=V(\mathcal{O})$, and, for any $\sigma\in\mathcal{I}$
and any set $\tau\subseteq V(\mathcal{O})$, we let
$\tau\in\Delta^{\prime}(\sigma)$ if $\tau$ is chromatic,
$\mbox{\sc{id}}(\tau)=\mbox{\sc{id}}(\sigma)$, $\tau\subseteq
V(\Delta(\sigma))$, and the local task $\Pi_{\tau,\sigma}$ is solvable in at
most one round in $M$. The simplices of $\mathcal{O}^{\prime}$ are the images
of $\Delta^{\prime}$, and all their faces.

Figure 2 illustrates Definition 2, and in particular of how the map
$\Delta^{\prime}$ is built. In this figure, the closure is with respect to the
immediate snapshot model, as witnessed by the fact that the complex
$\mathcal{P}^{(1)}(\tau)$ is the standard chromatic subdivision. We have
$\tau\in\Delta^{\prime}(\sigma)$ because the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta(\sigma),{\Delta}_{\tau,\sigma})$ is solvable
in one round with immediate snapshot, as there is a simplicial map
$f:\mathcal{P}^{(1)}(\tau)\to\Delta(\sigma)$ that respects
$\Delta_{\tau,\sigma}$: the chromatic subdivision of $\tau$ is mapped to the
dark subcomplex of $\Delta(\sigma)$ (the small letters specify $f$). Note that
the closure of a task depends on the communication model, as a local task
$\Pi_{\tau,\sigma}$ may be solvable in one round of some model $M$, but not of
some other model $M^{\prime}$.

Figure 2. Closure of a task

##### Remark.

Given a task $\Pi=(\mathcal{I},\mathcal{O},\Delta)$ and its closure
$\mbox{\footnotesize\sf
CL}_{M}(\Pi)=(\mathcal{I},\mathcal{O}^{\prime},\Delta^{\prime})$ w.r.t. some
model $M$, we have ${\Delta(\sigma)\subseteq\Delta^{\prime}(\sigma)}$ for
every $\sigma\in\mathcal{I}$. To see this, consider some
$\sigma\in\mathcal{I}$ and let $\tau\subseteq V(\mathcal{O})$ be a chromatic
set satisfying $\mbox{\sc{id}}(\tau)=\mbox{\sc{id}}(\sigma)$. If
$\tau\in\Delta(\sigma)$ (that is, $\tau$ is a simplex of $\Delta(\sigma)$)
then the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta(\sigma),{\Delta}_{\tau,\sigma})$ is solvable
in zero rounds, by having each process output its input.

Since ${\Delta(\sigma)\subseteq\Delta^{\prime}(\sigma)}$ for every
$\sigma\in\mathcal{I}$, the closure $\mbox{\footnotesize\sf
CL}_{M}(\Pi)=(\mathcal{I},\mathcal{O}^{\prime},\Delta^{\prime})$ of a task
$\Pi=(\mathcal{I},\mathcal{O},\Delta)$ is not more difficult that the task
itself. In the next subsection, we will show that the closure of a task is in
fact _simpler_ than the original task.

###  3.2. Asynchronous Speedup Theorem

We say that an iterated model $M$ _allows solo executions_ , if in every round
$t$ of Algorithm 1, for each process $i$, there is an execution where the
operations of process $i$ in round $t$ take place before the operations of all
the other processes in this round. Thus, there is an execution where process
$i$ reads only its own write in its collect operation.

###### Theorem 3.

Let $M$ be an iterated model allowing solo executions. For every $t\geq 1$, if
a task $\Pi$ is solvable in $t$ rounds in $M$, then the closure of $\Pi$ with
respect to $M$ is solvable in $t-1$ rounds in $M$.

###### Proof.

Let $\Pi=(\mathcal{I},\mathcal{O},\Delta)$ be a task on $n$ processes, let
$t\geq 1$, and assume that $\Pi$ is solvable in $t$ rounds in model $M$. Let
$\mbox{\footnotesize\sf
CL}_{M}(\Pi)=(\mathcal{I},\mathcal{O}^{\prime},\Delta^{\prime})$ be the
closure of $\Pi$ w.r.t. $M$. Our goal is to show that $\mbox{\footnotesize\sf
CL}_{M}(\Pi)$ is solvable in $t-1$ rounds in $M$.

Since $\Pi$ is solvable in $t$ rounds, there exists a simplicial map
$f:\mathcal{P}^{(t)}\to\mathcal{O}$ that agrees with $\Delta$. We aim at
defining a simplicial map
$f^{\prime}:\mathcal{P}^{(t-1)}\to\mathcal{O}^{\prime},$ that agrees with
$\Delta^{\prime}$. To this end, let $(i,V_{i})\in\mathcal{P}^{(t-1)}$ be a
vertex of $\mathcal{P}^{(t-1)}$, i.e., $V_{i}$ is a possible view of process
$i\in[n]$ after $t-1$ rounds (see Figure 3). We merely define
$f^{\prime}(i,V_{i})=f(i,\\{(i,V_{i})\\}).$ That is, $f^{\prime}(i,V_{i})$ is
equal to the image by $f$ of the vertex
$(i,\\{(i,V_{i})\\})\in\mathcal{P}^{(t)}$ resulting from
$(i,V_{i})\in\mathcal{P}^{(t-1)}$ whenever process $i$ runs solo at round $t$.
Note that $f(i,\\{(i,V_{i})\\})$ is a vertex of $\mathcal{O}$, and thus
$f^{\prime}(i,V_{i})$ is a vertex of $\mathcal{O}^{\prime}$, as
$V(\mathcal{O}^{\prime})=V(\mathcal{O})$.

Figure 3. Construction in the proof of Theorem 3

Let us show that $f^{\prime}$ is simplicial and agrees with $\Delta^{\prime}$.
To this end, let $\sigma\in\mathcal{I}$, and let

$\rho\in\mathcal{P}^{(t-1)}(\sigma),$

i.e., $\rho$ results from input $\sigma$ after $t-1$ rounds of communication
(see Figure 3). We aim at establishing that $f^{\prime}(\rho)$ is a simplex of
$\Delta^{\prime}(\sigma)$. Let us assume that $\sigma=\\{(i,x_{i}):i\in I\\}$
and

$\rho=\\{(i,V_{i}):i\in I\\},$

for some set $I\subseteq[n]$ of indices. Let us then consider
$\tau=f^{\prime}(\rho)$. For every $i\in I$, let
$(i,y_{i})=f^{\prime}(i,V_{i})$ be the output vertex returned by $f^{\prime}$
for process $i$ with view $V_{i}$ in $\mathcal{P}^{(t-1)}(\sigma)$. We have
$\tau=f^{\prime}(\rho)=\\{f^{\prime}(i,V_{i}):i\in I\\}=\\{(i,y_{i}):i\in
I\\}.$ To establish that $f^{\prime}$ is simplicial and agrees with
$\Delta^{\prime}$, it is sufficient to show that $\tau$ is a simplex of
$\Delta^{\prime}(\sigma)$.

To show that $\tau\in\Delta^{\prime}(\sigma)$, it is sufficient to show that
the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta(\sigma),{\Delta}_{\tau,\sigma})$ is solvable
in one round (cf. Definition 2), which we do next by presenting an algorithm.
The task $\Pi_{\tau,\sigma}$ is specific for $\tau$ and $\sigma$, and that
$\tau$ was chosen by first choosing $\rho\in\mathcal{P}^{(t-1)}(\sigma)$, so
when designing our algorithm we can use $\tau,\sigma$, and $\rho$. Moreover,
we use the existence of a $t$-round algorithm for $\Pi$, and the corresponding
decision map $f$. Intuitively, one can think of $\tau,\sigma,\rho$ and $f$ as
hard-coded in the algorithm.

Operationally, the following algorithm is solving the local task
$\Pi_{\tau,\sigma}$ in one round. For each $i\in\mbox{\sc{id}}(\tau)$, process
$i$ starts with input $y_{i}$. It performs one communication round and
collects a set $z_{i}=\\{(j,y_{j}):j\in J_{i}\\}$ with $i\in J_{i}\subseteq
I$. To compute its output value, process $i$ uses solely the set $J_{i}$ of
indices appearing in $z_{i}$ (and not the values collected), and, using
$\rho=\\{(i,V_{i}):i\in I\\}$, it computes the view $W_{i}=\\{(j,V_{j}):j\in
J_{i}\\}$. Then, process $i$ outputs $f(i,W_{i})$.

Topologically, we define a decision map
${g:\mathcal{P}^{(1)}(\tau)\to\Delta(\sigma)}$ as follows (see Figure 3). The
vertices of $\mathcal{P}^{(1)}(\tau)$ are in one-to-one correspondence with
the vertices of $\mathcal{P}^{(1)}(\rho)$, due to the canonical isomorphism
$\chi$ between $\mathcal{P}^{(1)}(\tau)$ and $\mathcal{P}^{(1)}(\rho)$ (cf.
Eq. (1)), and so we define $g=f\circ\chi$. The map $g$ is simplicial since $f$
and $\chi$ are simplicial. It remains to show that $g$ agrees with
${\Delta}_{\tau,\sigma}$, for which the two conditions of Definition 1 must be
fulfilled. First, let $(i,y_{i})$ be a vertex of $\tau$ for some
$i\in\mbox{\sc{id}}(\tau)$. We have

$g(i,\\{(i,y_{i})\\})=f(i,\\{(i,V_{i})\\})=f^{\prime}(i,V_{i})=(i,y_{i}).$

It follows that $g(i,\\{(i,y_{i})\\})\in{\Delta}_{\tau,\sigma}(i,y_{i})$
since, by definition, ${\Delta}_{\tau,\sigma}(i,y_{i})=\\{(i,y_{i})\\}$, and
Condition $1$ of Definition 1 is fulfilled. To check Condition $2$, let
$\tau^{\prime}\in\tau$ be a simplex of the input complex $\tau$ of the local
task $\Pi_{\tau,\sigma}$. In order to show that
$g(\mathcal{P}^{(1)}(\tau^{\prime}))\subseteq{\Delta}_{\tau,\sigma}(\tau^{\prime}),$
consider a simplex $\kappa^{\prime}\in\mathcal{P}^{(1)}(\tau^{\prime})$ with
$\mbox{\sc{id}}(\kappa^{\prime})=\mbox{\sc{id}}(\tau^{\prime})$, and let
$\rho^{\prime}=\chi(\kappa^{\prime})$ be the corresponding simplex in
$\mathcal{P}^{(1)}(\rho)$. By the definition of the map $g$, we have
$g(\kappa^{\prime})=f\circ\,\chi(\kappa^{\prime})=f(\rho^{\prime})$. Since $f$
solves the task $\Pi$ with input $\sigma\in\mathcal{I}$, we have
$f(\rho^{\prime})\in\Delta(\sigma)$. Since
$\mbox{\sc{id}}(f(\rho^{\prime}))=\mbox{\sc{id}}(\rho^{\prime})$, we get that
$f(\rho^{\prime})\in\mathsf{proj}_{\mbox{\footnotesize$\mbox{\sc{id}}$}(\tau^{\prime})}(\Delta(\sigma))$
as desired, and Condition $2$ of Definition 1 holds as well. It follows that
the map $g$ does solve the local task $\Pi_{\tau,\sigma}$ in a single round,
and therefore $\tau\in\Delta^{\prime}(\sigma)$. As a consequence, $f^{\prime}$
is simplicial and agrees with $\Delta^{\prime}$, which completes the proof. ∎

###  3.3. Impossibility of Consensus in the wait-free IIS Model

The speedup theorem enables to provide short proofs for classical
impossibility results or lower bounds, as illustrated below for Consensus. A
task $\Pi=(\mathcal{I},\mathcal{O},\Delta)$ is said to be a _fixed-point_ for
model $M$ whenever $\mbox{\footnotesize\sf CL}_{M}(\Pi)=\Pi$.

###### Lemma 0.

A task $\Pi$ that is a fixed-point for model $M$ is either solvable in zero
rounds in $M$, or unsolvable in $M$.

###### Proof.

Let us assume that there exists $t\geq 1$ such that $\Pi$ is solvable in $t$
rounds in $M$. By the speedup theorem, $\mbox{\footnotesize\sf
CL}_{M}(\Pi)=\Pi$ is solvable in $t-1$ rounds in $M$. By repeating the
application of the speedup theorem to $t-1,t-2,\dots,1$, we eventually get
that $\Pi$ is solvable in zero rounds in $M$. ∎

Recall that binary consensus task for $n$ processes is the task
$(\mathcal{I},\mathcal{O},\Delta)$ defined a follows. The input complex
$\mathcal{I}$ is composed of all simplices of the form
$\sigma=\\{(i,x_{i}):i\in I\\}$ for some nonempty set $I\subseteq[n]$ of
processes, where $x_{i}\in\\{0,1\\}$ for every $i\in I$. The output complex
$\mathcal{O}$ has two facets $\tau_{0}$ and $\tau_{1}$, where, for
$y\in\\{0,1\\}$, $\tau_{y}=\\{(i,y):i\in[n]\\}$. The set of legal output
simplices for the input simplex $\sigma=\\{(i,x_{i}):i\in I\\}\in\mathcal{I}$
is

$\Delta(\sigma)=\left\\{\begin{array}[]{ll}\\{\mathsf{proj}_{I}(\tau_{0}),\mathsf{proj}_{I}(\tau_{1})\\}&\mbox{if
there exists $i,j\in I$ such that $x_{i}\neq x_{j}$}\\\
\\{\sigma\\}&\mbox{otherwise.}\end{array}\right.$

###### Corollary 0.

Binary consensus is impossible to solve in the wait-free IIS model.

###### Proof.

Let $\Pi$ denote the binary consensus task, and let $M$ denote the wait-free
IIS model. For establishing the impossibility result, it is sufficient to show
that ${\mbox{\footnotesize\sf CL}_{M}(\Pi)=\Pi}$. After proving this, the
impossibility of consensus is immediate from Lemma 4, and the fact that binary
consensus is not solvable in zero rounds, simply because, in consensus, every
process running solo must output its input value, and, in a zero-round
algorithm, every process must output the same as if it was running solo.
Hence, our goal is to show that $\Delta^{\prime}(\sigma)=\Delta(\sigma)$ for
every $\sigma=\\{(i,x_{i}):i\in I\\}\in\mathcal{I}$. Since, as noticed before,
$\Delta(\sigma)\subseteq\Delta^{\prime}(\sigma)$ for every task, it suffices
to show $\Delta^{\prime}(\sigma)\subseteq\Delta(\sigma)$ for binary consensus.

Let $\tau=\\{(i,y_{i}):i\in I\\}\subseteq V(\Delta(\sigma))$ be such that
$\tau\in\Delta^{\prime}(\sigma)$, and let us show that
$\tau\in\Delta(\sigma)$. Assume first that $\sigma=\\{(i,x):i\in I\\}$ for
some $x\in\\{0,1\\}$. In this case, $\Delta(\sigma)=\sigma$, and thus, since
$\tau\subseteq V(\Delta(\sigma))$, we have $\tau=\sigma$, and thus
$\Delta^{\prime}(\sigma)=\Delta(\sigma)$. Assume now that $\sigma$ contains
two vertices with distinct input values $0$ and $1$. Our goal is to show that
$\tau$ cannot include two vertices $(i,y_{i})$ and $(j,y_{j})$ with $y_{i}\neq
y_{j}$. To this end, let $i,j\in I$ be two different indices. Since
$\tau\in\Delta^{\prime}(\sigma)$, the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta(\sigma),{\Delta}_{\tau,\sigma})$ is solvable
in a single round. So, let $f:\mathcal{P}^{(1)}(\tau)\to\Delta(\sigma)$ be a
simplicial map that agrees with ${\Delta}_{\tau,\sigma}$. Consider the path

$(i,\\{(i,y_{i})\\})\;\rule[2.0pt]{20.0pt}{1.0pt}\;(j,\\{(i,y_{i}),(j,y_{j})\\})\;\rule[2.0pt]{20.0pt}{1.0pt}\;(i,\\{(i,y_{i}),(j,y_{j})\\})\;\rule[2.0pt]{20.0pt}{1.0pt}\;(j,\\{(j,y_{j})\\})$

connecting the vertices $(i,\\{(i,y_{i})\\})$ and $(j,\\{(j,y_{j})\\})$ in
$\mathcal{P}^{(1)}(\tau)$. This path is composed of three distinct edges,
i.e., three distinct 1-dimensional simplices, $e_{1},e_{2}$, and $e_{3}$.
Since $f$ is simplicial, the image of this path by $f$ is a path connecting
the vertices $f(i,\\{(i,y_{i})\\})$ and $f(j,\\{(j,y_{j})\\})$. Since $f$
agrees with ${\Delta}_{\tau,\sigma}$, it holds that
$f(i,\\{(i,y_{i})\\})=(i,y_{i})$ and $f(j,\\{(j,y_{j})\\})=(j,y_{j})$.
Moreover, each of the (not necessarily distinct) edges $f(e_{k})$,
$k\in\\{1,2,3\\}$, must belong to
${\Delta}_{\tau,\sigma}(\\{(i,y_{i}),(j,y_{j})\\})=\mathsf{proj}_{\\{i,j\\}}(\Delta(\sigma))$.
We have
$\mathsf{proj}_{\\{i,j\\}}(\Delta(\sigma))=\\{\mathsf{proj}_{\\{i,j\\}}(\tau_{0}),\mathsf{proj}_{\\{i,j\\}}(\tau_{1})\\}$.
It follows that either all edges $f(e_{1})$, $f(e_{2})$, and $f(e_{3})$ are
equal to $\mathsf{proj}_{\\{i,j\\}}(\tau_{0})$, or all of them are equal to
$\mathsf{proj}_{\\{i,j\\}}(\tau_{1})$. As a consequence, $y_{i}=y_{j}$.
Therefore, all the output values in $\tau$ are identical, and thus
$\tau\in\Delta(\sigma)$, as desired. ∎

##  4\. Extensions of the Speedup Theorem

In order to design lower bounds or impossibility results to cases where
processes have access to an object solving some specific tasks (e.g., test-
and-set or binary consensus), we need to extend the speedup theorem to models
that use not only registers but also other communication objects, which we
informally call _black box_ objects.

###  4.1. Augmented Models

1 $V_{i}\leftarrow x_{i}$

2   __ for $r\leftarrow 1$ to $t$

3 $\mathbf{write}\;(i,V_{i})$ to $M_{r}[i]$

4 $a_{i}\leftarrow\alpha(i,V_{i},r)$

5 $b_{i}\leftarrow\mathbf{B}_{r}(a_{i})$

6 $C_{i}\leftarrow\mathbf{collect}\;M_{r}[1..n]$

7 $V_{i}\leftarrow(b_{i},C_{i})$

8 end

9$y_{i}\leftarrow f(i,V_{i})$

output $y_{i}$.

Algorithm 2 Code for process $i\in[n]$ with input $x_{i}$

We consider generic round-based algorithms in a model augmented with a black
box object $\mathbf{B}$ as displayed in Algorithm 2. This algorithm is similar
to Algorithm 1 except that a call to a black box $\mathbf{B}$ is inserted at
every round between the write and collect instructions. The calls performed at
two different rounds are independent, i.e., there are $t$ copies
$\mathbf{B}_{1},\dots,\mathbf{B}_{t}$ of $\mathbf{B}$, where $\mathbf{B}_{r}$
is the black box used by all processes at round $r$. Some of the black box
objects we use have input and output values, hence before invoking
$\mathbf{B}$ at a given round $r$, each process $i\in[n]$ computes an input
value $a_{i}$ for $\mathbf{B}_{r}$, which is chosen by a function $\alpha$
that takes into account the process $i$, its view $V_{i}$, and the round
number $r$. When process $i$ invokes $\mathbf{B}_{r}$ with input $a_{i}$, it
gets a value $b_{i}$ in return. To complete the round, process $i$ collects
the view of the other processes, and forms a new view which is the pair formed
by the value obtained from $\mathbf{B}_{r}$, and the collection of the views
of the other processes.

##### Remark.

In this paper, we assume that the black box object $\mathbf{B}$ is
_consistent_ in the sense that, for the same inputs to the processes, and for
the same interleaving of the reads and writes by the processes, $\mathbf{B}$
returns the same outputs to the processes. For instance, for the binary
consensus box where some processes provide the box with input 0, and some
others provide the box with input 1, the box will systematically produce the
same outputs, either all 0s, or all 1s, for the same interleaving. We may
assume consistency since we are only interested in lower bounds.

###  4.2. Extended Speedup Theorem

We say that an iterated model $M$ augmented with a black box _allows solo
executions_ , if in every round $t$ of Algorithm 2, for each process $i$,
there is an execution where the operations of process $i$ in round $t$ take
place before the operations of all other processes in this round.

###### Theorem 1.

Let $M$ be an iterated model augmented with a black box allowing solo
executions. For every $t\geq 1$, if a task $\Pi$ is solvable in $t$ rounds in
$M$, then the closure of $\Pi$ with respect to $M$ is solvable in $t-1$ rounds
in $M$.

###### Proof.

The proof is almost identical to the proof of Theorem 3, so we just underline
the changes. Given a simplicial map $f:\mathcal{P}^{(t)}\to\mathcal{O}$ that
agrees with $\Delta$, we define a simplicial map
$f^{\prime}:\mathcal{P}^{(t-1)}\to\mathcal{O}^{\prime},$ that agrees with
$\Delta^{\prime}$. Let $(i,V_{i})\in\mathcal{P}^{(t-1)}$ be a vertex of
$\mathcal{P}^{(t-1)}$. We define
$f^{\prime}(i,V_{i})=f\big{(}i,(b_{i},\\{(i,V_{i})\\})\big{)},$ where
$b_{i}=\mathbf{B}_{t}(a_{i})$ is the output of the black box $\mathbf{B}$
invoked at round $t$ with $a_{i}=\alpha(i,V_{i},t)$ as input, whenever process
$i$ is running solo in $\mathbf{B}$. Let us show that $f^{\prime}$ is
simplicial and agrees with $\Delta^{\prime}$. Let $\sigma=\\{(i,x_{i}):i\in
I\\}\in\mathcal{I}$ and $\rho=\\{(i,V_{i}):i\in
I\\}\in\mathcal{P}^{(t-1)}(\sigma)$, and let
$\tau=f^{\prime}(\rho)=\\{(i,y_{i}):i\in I\\}$. To show that
$\tau\in\Delta^{\prime}(\sigma)$, let us consider the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta(\sigma),{\Delta}_{\tau,\sigma})$, and let us
check that it is indeed solvable in one round. As in the proof of Theorem 3,
we define $g:\mathcal{P}^{(1)}(\tau)\to\Delta(\sigma)$ as $g=f\circ\chi$ where
$\chi:\mathcal{P}^{(1)}(\tau)\to\mathcal{P}^{(1)}(\rho)$ is the canonical
isomorphism. More specifically, every process $i\in I$ writes $y_{i}$ in
memory, calls the black box with input $a_{i}=\alpha(i,V_{i},t)$ to get a
value ${b_{i}=\mathbf{B}_{1}(a_{i})=\mathbf{B}_{t}(a_{i})}$ and collects a set
$z_{i}=\\{(j,y_{j}):j\in J_{i}\\}$ for some set $J_{i}$ with $i\in
J_{i}\subseteq I$. Process $i$ outputs
$g\big{(}i,(b_{i},z_{i})\big{)}=f\big{(}i,(b_{i},W_{i})\big{)}$ where
$W_{i}=\\{(j,V_{j}):j\in J_{i}\\}$. The fact that $g$ is simplicial and agrees
with ${\Delta}_{\tau,\sigma}$ follows exactly from the same arguments as in
the proof of Theorem 3, using the fact that the box is consistent — which
guarantees that, for every $\kappa\in\mathcal{P}^{(1)}(\tau)$, the outputs of
the box for $\kappa$ and for $\chi(\kappa)\in\mathcal{P}^{(1)}(\rho)$ are
identical. ∎

###  4.3. Impossibility of Consensus in the Wait-Free IIS Model with test&set

Recall that test&set is an object that requires no inputs, and every process
invoking test&set gets a value 0 or 1, with the guarantee that only the first
process to invoke it gets a 1, all the other getting 0. It is known that
test&set has consensus number 2 (Herlihy, 1991), i.e., it can be used to solve
binary consensus among two processes, but not among more processes. Multi-
value (i.e., not only binary) consensus among two processes can actually be
solved in a single round with test&set: A process receiving the value 1 from
test&set outputs its own input value, and a process receiving the value 0 from
test&set outputs the input value of the other process. Note that a process $i$
receiving the value 0 from test&set has the guarantee that the input value of
the other process was written in memory before process $i$ performs a
snapshot, as if it was not running test&set solo (if the process would have
run test&set solo, it would have obtained the value 1 from test&set).

Figure 4 illustrates why 2-process binary consensus is solvable with access to
a test&set object. After one round, every process $i\in\\{1,2\\}$ which sees
only itself when reading the shared memory must win in test&set, and thus gets
a view $(1,\\{(i,x_{i})\\})$, where $x_{i}\in\\{0,1\\}$ is the input of
process $i$. Every process $i$ which saw the other process $j$ gets a view
$(b_{i},\\{(i,x_{i}),(j,x_{j})\\})$ where $x_{i}$ and $x_{j}$ are the input
values of processes $i$ and $j$, respectively, and $b_{i}\in\\{0,1\\}$ is the
value produced by test&set for process $i$. The mapping
$f:\mathcal{P}^{(1)}\to\mathcal{O}$ displayed on Figure 4 is simplicial, and
its composition with the map $\Xi:\mathcal{I}\to\mathcal{P}^{(1)}$ agrees with
the specification of consensus.

Figure 4. 2-process binary consensus is solvable using test&set

In contrast, we show that for more than two processes, binary consensus is not
solvable even using test&set, by applying Theorem 1. Figure 5 describes the
protocol complex $\mathcal{P}^{(1)}(\sigma)$ for a 2-dimensional simplex
$\sigma$ for the immediate snapshot model augmented with test&set. For each
$i\in\\{1,2,3\\}$, instead of four vertices with same ID $i$ as in the
12-vertex chromatic subdivision of the triangle resulting from immediate
snapshot, Figure 5 displays seven vertices with the same ID $i$, each vertex
of the chromatic subdivision being duplicated depending on the outcome 0 or 1
of test&set, except the vertex corresponding to a solo execution for which the
outcome of test&set is necessarily 1.

Figure 5. 1-round protocol complex for three processes using test&set

###### Corollary 0.

For every $n>2$, binary consensus among $n$ processes is impossible to solve
in the wait-free IIS model augmented with test&set.

###### Proof.

Let $M$ be the model of iterated immediate snapshot with a test&set object. We
cannot proceed exactly as in the proof of Corollary 5, as the binary consensus
task $\Pi_{\text{\tiny CON}}=(\mathcal{I},\mathcal{O},\Delta)$ for $n>2$
processes is not formally a fixed point for $M$. The reason for this is that,
in $\Pi_{\text{\tiny CON}}$, even if only two processes $i$ and $j$
participate, they must agree on the same value, while in the closure task
$\mbox{\footnotesize\sf CL}_{M}(\Pi_{\text{\tiny
CON}})=(\mathcal{I},\mathcal{O}^{\prime},\Delta^{\prime})$ this is not the
case. Formally, since $2$-process consensus is solvable using test&set in one
round, for $\sigma=\\{(i,0),(j,1)\\}$ we have
$\Delta^{\prime}(\sigma)=\big{\\{}\\{(i,y_{i}),(j,y_{j})\\}:(y_{i},y_{j})\in\\{0,1\\}^{2}\big{\\}}$.

Let us instead consider the simpler task
$\Pi=(\mathcal{I},\mathcal{O},\Delta)$, where the input and output values and
complexes are as in consensus, the validity condition must still be fulfilled
(every output value must be an input value), but, only if at least three
processes participate, they must output the same value. Every consensus
algorithm also solves this problem, so it is enough to prove the impossibility
of $\Pi$. We now prove that $\Pi$ is a fixed point of $M$.

Let $\mbox{\footnotesize\sf
CL}_{M}(\Pi)=(\mathcal{I},\mathcal{O}^{\prime},\Delta^{\prime})$ be the
closure task of $\Pi$. Let us fix simplices $\sigma=\\{(i,x_{i})\mid i\in
I\\}\in\mathcal{I}$ and $\tau=\\{(i,y_{i}),\mid i\in
I\\}\in\Delta^{\prime}(\sigma)$ for a non-empty set $I\subseteq[n]$. If
$|I|\leq 2$, then any subset of $\tau^{\prime}\subseteq V(\Delta(\sigma))$ is
already a simplex of $\Delta(\sigma)$, and we are done. Let us now consider
the case of $|I|\geq 3$. Let $i,j,k\in I$, and let $y_{i},y_{j},y_{k}$ be the
values associated with the three processes $i,j,k$ in $\tau$. Our goal is to
show that $y_{i}=y_{j}=y_{k}$, which will imply that $\tau\in\Delta(\sigma)$.

By the definition of a closure of a task, we know that the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta(\sigma),{\Delta}_{\tau,\sigma})$ is solvable
in one round. Let $f:\mathcal{P}^{(1)}\to\mathcal{O}$ be a simplicial map
solving $\Pi_{\tau,\sigma}$. For every $v=(\ell,y_{\ell})\in\tau$, $\ell\in
I$, we have ${\Delta}_{\tau,\sigma}(v)=\\{v\\}$, hence
$f\big{(}\ell,(t_{\ell},\\{\ell,y_{\ell})\\})\big{)}=(\ell,y_{\ell})$, where
$t_{\ell}$ is the output of test&set, which is actually equal to $1$ since the
vertex $\big{(}\ell,(t_{\ell},\\{(\ell,y_{\ell})\\})\big{)}$ represents a solo
step by process $\ell$.

In $\mathcal{P}^{(1)}(\sigma)$, let us consider the two simplices (see Figure
6)

$\rho_{i,j,k}=\Big{\\{}\big{(}i,(1,\\{(i,y_{i})\\})\big{)},\big{(}j,(0,\\{(i,y_{i}),(j,y_{j})\\})\big{)},\big{(}k,(0,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\})\big{)}\Big{\\}},$

and

$\rho_{j,i,k}=\Big{\\{}\big{(}j,(1,\\{(j,y_{j})\\})\big{)},\big{(}i,(0,\\{(i,y_{i}),(j,y_{j})\\})\big{)},\big{(}k,(0,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\})\big{)}\Big{\\}}.$

Let $\gamma=f\big{(}k,(0,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\})\big{)}$ be the
output of $f$ on the vertex
$\big{(}k,(0,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\})\big{)}$ of
$\mathcal{P}^{(1)}(\sigma)$. Since $f$ agrees with $\Delta_{\tau,\sigma}$, we
have that
$f(\rho_{i,j,k})\subseteq\mathsf{proj}_{\\{i,j,k\\}}(\Delta(\sigma))$, and the
definition of $\Delta$ implies that, in $\Delta(\sigma)$, all processes output
the same value $y_{i}=\gamma$. A similar argument on $f(\rho_{j,i,k})$ implies
that $y_{j}=\gamma$, i.e., $y_{i}=y_{j}$. By applying this argument for every
$\ell\in I$, we get that all processes decide the same value $\gamma$ in
$\tau$, that is, $\tau=\\{(\ell,\gamma)\mid\ell\in I\\}$, which implies that
$\tau\in\Delta(\sigma)$, as claimed.

The rest of the proof is similar to the proof of Lemma 4, but using Theorem 1.
That is, if $\Pi$ was solvable in $t$ rounds in $M$ among $n\geq 3$ processes,
then $\Pi$ would have also been solvable in $t-1$ rounds, and, similarly, in
$0$ rounds. Since this is not the case, $\Pi$ is not solvable in $M$ at all.
As mentioned above, $\Pi$ is simpler than consensus, and so, for $n\geq 3$
processes, consensus is not solvable. ∎

Figure 6. Consensus is not solvable among $n>2$ processes, even using test&set

##  5\. Lower Bounds for Approximate Agreement

In this section, we apply our speedup theorem, and its extension, to the
_approximate agreement_ task. This task is a relaxation of the consensus
problems, where processes have to decide on values that in the interval
defined by the input values, and are close to one another (but not necessarily
identical as in consensus). Given a (small) real value $\epsilon>0$, in order
to accurately define the $\epsilon$-approximate agreement task while using
only finite topological objects, we assume that $\epsilon$ and all the input
values are rational numbers in the interval $[0,1]$. Specifically, we
discretize this interval as follows. We choose a (large) integer $m\geq
1/\epsilon$ such that $\epsilon$ is an integral multiple of $1/m$ (i.e.,
$m\epsilon$ is an integer), and so are all the possible input values of the
task. We make sure that all the output values are also integral multiples of
$1/m$. To this end, we avoid the usage of averaging algorithms, which are
common in other works on approximate agreement. We formally define $\epsilon$
approximate agreement as follows.

###### Definition 0.

Given a parameter $\epsilon\in(0,1]$ which is an integral multiple of $1/m$
for some integer $m\geq 1$, the _$\epsilon$ -approximate agreement_ for $n$
processes is the task $(\mathcal{I},\mathcal{O},\Delta)$, where

$\displaystyle\mathcal{I}=\big{\\{}\\{(i,x_{i}):i\in I\\}\mid(\varnothing\neq
I\subseteq[n])\;\wedge\;(\forall i\in
I,\;x_{i}\in\\{0,1/m,2/m,\ldots,1\\})\big{\\}}$
$\displaystyle\mathcal{O}=\big{\\{}\\{(i,y_{i}):i\in I\\}\mid(\varnothing\neq
I\subseteq[n]),\;(\forall i\in
I,y_{i}\in\\{0,1/m,2/m,\ldots,1\\})\;\wedge\;(\forall i,j\in
I,|y_{i}-y_{j}|\leq\epsilon)\big{\\}}$ $\displaystyle\Delta:\mathcal{I}\to
2^{\mathcal{O}}\text{ where }\Delta\big{(}\\{(i,x_{i}):i\in
I\\}\big{)}=\big{\\{}\\{(i,y_{i}):i\in I\\}\in\mathcal{O}\mid\forall j\in
I,\min\\{x_{i}:i\in I\\}\leq y_{j}\leq\max\\{x_{i}:i\in I\\}\big{\\}}$

We are interested in solving approximate agreement when the processes have
access to an object that can be used in order to solve consensus among two
processes, and hence also $\epsilon$-approximate agreement for every
$\epsilon$. This creates a technical difficulty when applying our speed up
technique, even when more than two processes are present. To overcome this, we
define a relaxed version of $\epsilon$-approximate agreement, where if exactly
two processes participate, then they only need to output values in the range
of inputs, but there is no bound on the distance between them.

###### Definition 0.

The _liberal version of $\epsilon$-approximate agreement_ is identical to the
$\epsilon$-approximate agreement task, except that the output complex
$\mathcal{O}$ contains also all $1$-dimensional chromatic simplices,
regardless of the distances between their values. The map $\Delta$ specifying
the task is formally defined the same, which means that for $1$-dimensional
input simplices it now contains more allowed output simplices.

In fact, this is the type of relaxation we apply on the consensus task in the
proof of Corollary 2. Note that any algorithm solving $\epsilon$-approximate
agreement also solves the liberal version of $\epsilon$-approximate agreement,
hence any lower bound for the latter implies a lower bound for the former.

###  5.1. Approximate Agreement in the Wait-Free IIS Model

Using our tools, we can easily reprove the fact that $\epsilon$-approximate
agreement takes $\Omega(\log 1/\epsilon)$ rounds in the standard IIS model
(Hoest and Shavit, 2006). For this, we show that the closure of
$\epsilon$-approximate agreement for two processes is
$(3\epsilon)$-approximate agreement, and $(2\epsilon)$-approximate agreement
for more processes. We start by proving some claims — the first of them is
almost a triviality.

###### Claim 1.

For $\epsilon<1$, $\epsilon$-approximate agreement is not solvable in $0$
rounds, and so is the liberal version of $\epsilon$-approximate agreement for
$n\geq 3$ processes.

###### Proof.

Let $\epsilon<1$, and assume for contradiction that there is a $0$-round
$\epsilon$-approximate agreement algorithm, or a $0$-round algorithm solving
the liberal version of $\epsilon$-approximate agreement among $n\geq 3$
processes. Consider a setting with inputs $(1,0)$ and $(2,1)$, i.e., where
process $1$ has input $0$ and process $2$ has input $1$. In a solo-execution
each process must output its own input, and the setting where several
processes run is indistinguishable to them from the one where each runs solo,
so they will output $0$ and $1$ in all cases, contradicting the task
definition. Formally, we have $\Delta(\\{(1,0)\\})=\\{(1,0)\\}$ and
$\Delta(\\{(2,1)\\}))=\\{(2,1)\\}$. As $\Xi:\mathcal{I}\to\mathcal{P}^{(0)}$
is simply the identity map, in a $0$-round protocol any decision map $f$ goes
directly from $\mathcal{I}$ to $\mathcal{O}$. Hence, any decision map
$f:\mathcal{I}\to\mathcal{O}$ must satisfy $f(1,0)=(1,0)$ and $f(2,1)=(2,1)$.

For the original $\epsilon$-approximate agreement task, this implies that the
input simplex $\sigma=\\{(1,0),(2,1)\\}$, is mapped to
$f(\sigma)=\\{(1,0),(2,1)\\}\notin\Delta(\sigma)$ (in fact, we even have
$f(\sigma)\notin\mathcal{O}$). For the liberal version of the task and $n\geq
3$, consider the same setting but with an extra “dummy” process $3$, with
input $0$. As before, $f(3,0)=(3,0)$, and
$f(\\{(1,0),(2,1),(3,0)\\})=\\{(1,0),(2,1),(3,0)\\}\notin\Delta(\sigma)$,
where here $\Delta$ is the specification of the liberal version of
$\epsilon$-approximate agreement. Hence, in both cases no algorithm and
decision map $f$ can solve the problem. ∎

The next claim is about the closure of approximate agreement in the specific
case of two processes.

###### Claim 2.

If $\Pi$ is the $\epsilon$-approximate agreement task for two processes, then
$\mbox{\footnotesize\sf CL}_{M}(\Pi)$ w.r.t. the wait-free IIS model $M$ is
the $(3\epsilon)$-approximate agreement task for two processes.

###### Proof.

Let $\Pi_{\epsilon}=(\mathcal{I},\mathcal{O}_{\epsilon},\Delta_{\epsilon})$ be
the $\epsilon$-approximate agreement task for $n=2$ processes, and let
$\mbox{\footnotesize\sf
CL}_{M}(\Pi_{\epsilon})=(\mathcal{I},\mathcal{O}^{\prime}_{\epsilon},\Delta^{\prime}_{\epsilon})$
be its closure in the considered model $M$. Let us denote the
$(3\epsilon)$-approximate agreement task by
$\Pi_{3\epsilon}=(\mathcal{I},\mathcal{O}_{3\epsilon},\Delta_{3\epsilon})$. We
want to show that, for every $\sigma\in\mathcal{I}$,
$\Delta^{\prime}_{\epsilon}(\sigma)=\Delta_{3\epsilon}(\sigma)$. We consider
separately the cases where $\sigma$ is a vertex, and $\sigma$ is an edge
(recall that we are in the setting involving $n=2$ processes).

Let $\sigma\in\mathcal{I}$ be a vertex. Let
$\tau\in\Delta^{\prime}_{\epsilon}(\sigma)$, which immediately implies
$\tau\in\Delta_{\epsilon}(\sigma)$. As $\sigma$ is a vertex, we have
$\Delta_{\epsilon}(\sigma)=\\{\sigma\\}$, from which we derive $\tau=\sigma$.
We also have $\Delta_{3\epsilon}(\sigma)=\\{\sigma\\}$, and hence
$\tau\in\Delta_{3\epsilon}(\sigma)$. Conversely, let
$\tau\in\Delta_{3\epsilon}(\sigma)$, and again
$\Delta_{3\epsilon}(\sigma)=\\{\sigma\\}$ implies $\tau=\sigma$. The local
task $(\sigma,\Delta_{\epsilon}(\sigma),\Delta_{\sigma,\sigma})$ is trivially
solvable in one round—it is even solvable in zero rounds using the mapping
$f(\sigma)=\sigma$—and hence $\tau\in\Delta^{\prime}_{\epsilon}(\sigma)$. We
conclude that for vertices, $\Delta^{\prime}_{\epsilon}$ and
$\Delta_{3\epsilon}$ are identical.

Let $\sigma=\\{(1,x_{1}),(2,x_{2})\\}\in\mathcal{I}$ be an edge. We consider
an edge $\tau=\\{(1,y_{1}),(2,y_{2})\\}\in\Delta_{\epsilon}^{\prime}(\sigma)$,
and show $\tau\in\Delta_{3\epsilon}(\sigma)$. To this end, we show (1)
$\min\\{x_{1},x_{2}\\}\leq y_{i}\leq\max\\{x_{1},x_{2}\\}$ for all
$i\in\\{1,2\\}$, and (2) $|y_{1}-y_{2}|\leq 3\epsilon$. Since
$\tau\in\Delta_{\epsilon}^{\prime}(\sigma)$, the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$ is
solvable in one round, and let
$f:\mathcal{P}^{(1)}(\tau)\to\Delta_{\epsilon}(\sigma)$ be a simplicial map
solving it. Since $\tau\subseteq V(\Delta_{\epsilon}(\sigma))$, we know that
every vertex $v=(i,y_{i})\in\tau$, $i\in\\{1,2\\}$, satisfies
$\min\\{x_{1},x_{2}\\}\leq y_{i}\leq\max\\{x_{1},x_{2}\\}$, and thus property
(1) holds. Let us denote by $\gamma_{1},\gamma_{2}$ the two values satisfying

$\begin{array}[]{rcl}f(1,\\{(1,y_{1})\\})&=&(1,y_{1}),\\\
f(2,\\{(1,y_{1}),(2,y_{2})\\})&=&(2,\gamma_{2}),\\\
f(1,\\{(1,y_{1}),(2,y_{2})\\})&=&(1,\gamma_{1}),\\\
f(2,\\{(2,y_{2})\\})&=&(2,y_{2}).\end{array}$

Since $f$ solves the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$,
we have
$|y_{2}-y_{1}|\leq|y_{2}-\gamma_{1}|+|\gamma_{1}-\gamma_{2}|+|\gamma_{2}-y_{1}|\leq
3\epsilon$. Property (2) thus holds as well, implying
$\tau\in\Delta_{3\epsilon}(\sigma)$.

Conversely, let us consider
$\tau=\\{(1,y_{1}),(2,y_{2})\\}\in\Delta_{3\epsilon}(\sigma)$, and let us
assume, w.l.o.g., that $y_{1}\leq y_{2}$. Let
$f:\mathcal{P}^{(1)}(\tau)\to\Delta_{\epsilon}(\sigma)$ defined as follows, by
setting $z=\min\\{y_{2},y_{1}+\epsilon\\}$, and

(2) $\begin{array}[]{rcl}f(1,\\{(1,y_{1})\\})&=&(1,y_{1}),\\\
f(2,\\{(1,y_{1}),(2,y_{2})\\})&=&(2,z),\\\
f(1,\\{(1,y_{1}),(2,y_{2})\\})&=&(1,\min\\{y_{2},z+\epsilon\\}),\\\
f(2,\\{(2,y_{2})\\})&=&(2,y_{2}).\end{array}$

The map $f$ solves $\epsilon$-approximate agreement whenever $y_{2}-y_{1}\leq
3\epsilon$, and therefore it solves the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$ in
one round. It follows that $\tau\in\Delta^{\prime}_{\epsilon}(\sigma)$. We
conclude that, for edges as well, $\Delta^{\prime}_{\epsilon}$ and
$\Delta_{3\epsilon}$ are identical. ∎

The next claim is about the closure of the liberal version of approximate
agreement in the case of three or more processes.

###### Claim 3.

If $\Pi=(\mathcal{I},\mathcal{O},\Delta)$ is the liberal version of
$\epsilon$-approximate agreement with $n\geq 3$ processes, then the closure
$\mbox{\footnotesize\sf CL}_{M}(\Pi)$ of $\Pi$ with respect to the wait-free
IIS model $M$ is the liberal version of $(2\epsilon)$-approximate agreement.

###### Proof.

Let $\Pi_{\epsilon}=(\mathcal{I},\mathcal{O}_{\epsilon},\Delta_{\epsilon})$ be
the liberal version of $\epsilon$-approximate agreement with $n\geq 3$
processes, and let $\mbox{\footnotesize\sf
CL}_{M}(\Pi_{\epsilon})=(\mathcal{I},\mathcal{O}^{\prime}_{\epsilon},\Delta^{\prime}_{\epsilon})$.
Let us denote the liberal version of $(2\epsilon)$-approximate agreement by
$\Pi_{2\epsilon}=(\mathcal{I},\mathcal{O}_{2\epsilon},\Delta_{2\epsilon})$. We
want to show that, for every $\sigma\in\mathcal{I}$,
$\Delta^{\prime}_{\epsilon}(\sigma)=\Delta_{2\epsilon}(\sigma)$. If $\sigma$
is a vertex, this equality holds exactly by the same reasoning as in the proof
of Claim 2. We hence focus on the case where $|\sigma|\geq 2$.

Fix an input simplex $\sigma=\\{(i,x_{i})\mid i\in I\\}\in\mathcal{I}$, for
some non-empty set $I\subseteq[n]$. If $|I|=1$, i.e., $I=\\{i\\}$, then
$\sigma=\\{(i,x_{i})\\}\in\mathcal{I}$, and
$\Delta^{\prime}_{\epsilon}(\\{(i,x_{i})\\})=\\{(i,x_{i})\\}=\Delta_{2\epsilon}(\\{(i,x_{i})\\})$.
If $|I|=2$, then the fact that the liberal version of the tasks does not
depend on $\epsilon$ makes the maps equal:
$\Delta^{\prime}_{\epsilon}(\sigma)=\\{(j,y_{j})\mid j\in
I,\;\min\\{x_{i}:i\in I\\}\leq y_{j}\leq\max\\{x_{i}:i\in
I\\}\\}=\Delta_{2\epsilon}(\sigma)$. For the case $|I|\geq 3$, we prove
containment in both directions. First, we consider a simplex
$\tau=\\{(i,y_{i})\mid i\in I\\}\in\Delta_{\epsilon}^{\prime}(\sigma)$, and
show $\tau\in\Delta_{2\epsilon}(\sigma)$, i.e., (1) $\min\\{x_{i}:i\in
I\\}\leq y_{i^{\prime}}\leq\max\\{x_{i}:i\in I\\}$ for all $i^{\prime}\in I$,
and (2) $|y_{i}-y_{i^{\prime}}|\leq 2\epsilon$ for all $i,i^{\prime}\in I$.
Since $\tau\in\Delta_{\epsilon}^{\prime}(\sigma)$, the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$ is
solvable in one round, and let
$f:\mathcal{P}^{(1)}(\tau)\to\Delta_{\epsilon}(\sigma)$ be a simplicial map
solving it. As before, for every $v=(i,y_{i})\in\tau$, $i\in I$, we have
${\Delta}_{\tau,\sigma}(v)=\\{v\\}$ and $v\in\Delta_{\epsilon}(\sigma)$, i.e.,
$f(i,\\{(i,y_{i})\\})=(i,y_{i})$, and thus property (1) holds. To check
property (2), let us consider three processes $i,j,k\in I$, and let $\gamma$
be such that $f(k,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\})=(k,\gamma)$. Then

$\begin{array}[]{rcl}f(i,\\{(i,y_{i})\\})&=&(i,y_{i}),\\\
f(j,\\{(j,y_{j})\\})&=&(j,y_{j}),\\\
f(k,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\})&=&(k,\gamma).\end{array}$

Since $f$ solves the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$,
we have $|y_{i}-y_{j}|\leq|y_{j}-\gamma|+|\gamma-y_{i}|\leq 2\epsilon$. It
follows that $\tau\in\Delta_{2\epsilon}(\sigma)$.

Conversely, let us consider $\tau=\\{(i,y_{i})\mid i\in
I\\}\in\Delta_{2\epsilon}(\sigma)$, and let us define
$f:\mathcal{P}^{(1)}(\tau)\to\Delta_{\epsilon}(\sigma)$ by setting, for every
$i\in I$ and every set $J\subseteq I$ satisfying $i\in J$,

(3) $f(i,\\{y_{j}:j\in J\\})=\Big{(}i,\min\big{\\{}\max\\{y_{j}:j\in
J\\},\min\\{y_{j}:j\in J\\}+\epsilon\big{\\}}\Big{)}.$

To show that this map $f$ solves the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$ in
one round, it is sufficient to show that $f$ solves $\epsilon$-approximate
agreement whenever the inputs are at distance at most $2\epsilon$ apart from
each other. So, let us consider two processes $i,i^{\prime}$, and let
$J,J^{\prime}$ be the sets of processes that these two processes see in their
immediate snapshot, respectively. Assume, w.l.o.g., that $J^{\prime}\subseteq
J$ (this must be the case for outputs of immediate snapshot). Let $y_{\min}$
and $y_{\max}$ be the minimal and maximal values in $\\{y_{j}\mid j\in J\\}$,
and let $y^{\prime}_{\min}$ and $y^{\prime}_{\max}$ be the minimal and maximal
values in $\\{y^{\prime}_{j}\mid j\in J^{\prime}\\}$. Note that $y_{\min}\leq
y^{\prime}_{\min}\leq y^{\prime}_{\max}\leq y_{\max}\leq y_{\min}+2\epsilon$.
If $y^{\prime}_{\max}\leq y_{\min}+\epsilon$ then the facts that
$f(i,\\{y_{j}:j\in J\\})\leq y_{\min}+\epsilon$ and $f(i,\\{y_{j}:j\in
J^{\prime}\\})\leq y^{\prime}_{\max}$ imply that both processes output values
in $[y_{\min},y_{\min}+\epsilon]$, and we are done. Otherwise,
$y_{\min}+\epsilon<y^{\prime}_{\max}\leq y_{\max}$, and so process $i$ outputs
$y_{\min}+\epsilon$, while process $i^{\prime}$ outputs a value in
$[y_{\min},y_{\min}+2\epsilon]$, and we are done too.

We conclude that $\Delta^{\prime}_{\epsilon}$ and $\Delta_{2\epsilon}$ are
identical on simplices of all sizes. ∎

We are now ready to prove a lower bound for approximate agreement.

###### Corollary 0.

The number of rounds required for solving the $\epsilon$-approximate agreement
task in the wait-free IIS model with $n$ processes is at least
$\lceil\log_{3}(1/\epsilon)\rceil$ if $n=2$, and
$\lceil\log_{2}(1/\epsilon)\rceil$ if $n>2$.

###### Proof.

Fix $\epsilon$ and $n$, and let $\Pi$ denote the $\epsilon$-approximate
agreement task. Consider an algorithm solving $\epsilon$-approximate agreement
in $t$ rounds. If $n=2$, then, by Theorem 3 and Claim 2, there is an algorithm
solving $(3\epsilon)$-approximate agreement in $t-1$ rounds. By repeating this
argument $t$ times, we get a $(3^{t}\epsilon)$-approximate agreement algorithm
running in $0$ rounds. By Claim 1, we have $3^{t}\epsilon\geq 1$, which
immediately implies the lower bound. If $n\geq 3$, first note that the alleged
algorithm also solves the liberal version of $\epsilon$-approximate agreement
in $t$ rounds. By the same proof as above, but using Claim 3 instead of Claim
2, we get that there is a $0$-round algorithm solving the liberal version of
$(2^{t}\epsilon)$-approximate agreement, implying $2^{t}\epsilon\geq 1$, and
the lower bound follows. ∎

##### Remark.

The bounds in Corollary 3 are known to be tight (Hoest and Shavit, 2006). In
fact, the tightness of our lower bounds is also directly implied by our
proofs, as specified by Equations 2 and 3. The former is for two processes,
and essentially divides the distances by 3 at each round. The latter is for
three or more processes, and essentially halves the distances at each round.

###  5.2. Approximate Agreement in the Wait-Free IIS Model Augmented with
test&set

We now turn our attention to the approximate agreement task in an augmented
version of the previous model, namely, we consider a model of iterated
immediate snapshot augmented with test&set. It is known that the consensus
number of test&set is $2$, and, as explained in the previous section, in the
model of immediate snapshot augmented with test&set, consensus among two
processes can be solved in a single round. This immediately implies that the
simpler task of approximate agreement among two processes is also solvable in
a single round in this model. A more surprising result asserts that with three
or more processes, the test&set object does not accelerate much the solution
of approximate agreement. Indeed, using the round reduction theorem for
augmented models (Theorem 1), we show that it still takes at least
$\lceil\log_{2}1/\epsilon\rceil$ rounds to solve $\epsilon$-approximate
agreement.

###### Theorem 4.

The number of rounds required for solving the $\epsilon$-approximate agreement
task in the wait-free IIS model augmented with test&set among $n\geq 3$
processes is at least $\lceil\log_{2}(1/\epsilon)\rceil$.

###### Proof.

To establish the theorem, we first prove an analogue of Claim 3, for the model
of iterated immediate snapshot augmented with test&set.

###### Claim 4.

If $\Pi=(\mathcal{I},\mathcal{O},\Delta)$ is the liberal version of
$\epsilon$-approximate agreement with $n\geq 3$ processes, then the closure of
$\Pi$ with respect to the wait-free IIS model augmented with test&set is the
liberal version of $(2\epsilon)$-approximate agreement.

###### Proof of claim.

Let $\Pi_{\epsilon}=(\mathcal{I},\mathcal{O}_{\epsilon},\Delta_{\epsilon})$ be
the liberal version of $\epsilon$-approximate agreement for $n\geq 3$
processes, and let $\mbox{\footnotesize\sf
CL}_{M}(\Pi_{\epsilon})=(\mathcal{I},\mathcal{O}^{\prime}_{\epsilon},\Delta^{\prime}_{\epsilon})$
be the closure of $\Pi_{\epsilon}$ in the considered model $M$. Let us denote
the liberal version of $(2\epsilon)$-approximate agreement by
$\Pi_{2\epsilon}=(\mathcal{I},\mathcal{O}_{2\epsilon},\Delta_{2\epsilon})$. We
want to show that, for every $\sigma\in\mathcal{I}$,
$\Delta^{\prime}_{\epsilon}(\sigma)=\Delta_{2\epsilon}(\sigma)$. If
$|\sigma|\leq 2$, this equality holds exactly by the same reasoning as in the
previous proofs (Claim 2 for $|\sigma|=1$ and Claim 3 for $|\sigma|=2$), so we
focus on the case where $|\sigma|\geq 3$.

Consider an input simplex $\sigma=\\{(i,x_{i})\mid i\in I\\}\in\mathcal{I}$,
for some set $I\subseteq[n]$, $|I|\geq 3$. We consider a simplex
$\tau=\\{(i,y_{i})\mid i\in I\\}\in\Delta_{\epsilon}^{\prime}(\sigma)$, and
show $\tau\in\Delta_{2\epsilon}(\sigma)$, i.e., (1) $\min\\{x_{i}:i\in
I\\}\leq y_{i}\leq\max\\{x_{i}:i\in I\\}$ for all $i\in I$, and (2)
$|y_{i}-y_{j}|\leq 2\epsilon$ for all $i,j\in I$. Since
$\tau\in\Delta_{\epsilon}^{\prime}(\sigma)$, the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$ is
solvable in one round, and let
$f:\mathcal{P}^{(1)}(\tau)\to\Delta_{\epsilon}(\sigma)$ be a simplicial map
solving it. As before, $\tau\subseteq V(\Delta_{\epsilon}(\sigma))$ implies
property (1). To check property (2), let us focus on the simplices of
$\mathcal{P}^{(1)}(\sigma)$ considered in the proof of Corollary 2 (see also
Figure 6):

$\displaystyle\rho_{i,j,k}=\Big{\\{}\big{(}i,(1,\\{(i,y_{i})\\})\big{)},\big{(}j,(0,\\{(i,y_{i}),(j,y_{j})\\})\big{)},\big{(}k,(0,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\})\big{)}\Big{\\}},$
$\displaystyle\rho_{j,i,k}=\Big{\\{}\big{(}j,(1,\\{(j,y_{j})\\})\big{)},\big{(}i,(0,\\{(i,y_{i}),(j,y_{j})\\})\big{)},\big{(}k,(0,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\})\big{)}\Big{\\}}.$

Let $(k,\gamma)=f\big{(}k,(0,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\})\big{)}$ be
the output at vertex
$\big{(}k,(0,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\})\big{)}$. Since $f$ agrees
with $\Delta_{\tau,\sigma}$, we have that
$f(\rho_{i,j,k})\subseteq\mathsf{proj}_{\\{i,j,k\\}}(\Delta_{\epsilon}(\sigma))$,
and the definition of $\Delta_{\epsilon}$ implies
$|y_{i}-\gamma|\leq\epsilon$. A similar argument on $f(\rho_{j,i,k})$ implies
$|y_{j}-\gamma|\leq\epsilon$, and the triangle inequality hence implies
$|y_{i}-y_{j}|\leq 2\epsilon$, as desired.

Conversely, let us consider $\tau=\\{(i,y_{i})\mid i\in
I\\}\in\Delta_{2\epsilon}(\sigma)$, and let us define
$f:\mathcal{P}^{(1)}(\tau)\to\Delta_{\epsilon}(\sigma)$ in a very similar way
to the one in the proof of Claim 3, ignoring the output $t_{i}$ of the
test&set object. That is, for every $i\in I$ and every set $J\subseteq I$
satisfying $i\in J$, we set

$f\big{(}i,(t_{i},\\{(j,y_{j})\mid j\in
J\\})\big{)}=\Big{(}i,\min\big{\\{}\max\\{y_{j}:j\in J\\},\min\\{y_{j}:j\in
J\\}+\epsilon\big{\\}}\Big{)}.$

As for the proof of Claim 3, this map $f$ solves $\epsilon$-approximate
agreement whenever $|y_{i}-y_{j}|\leq 2\epsilon$ for every $i,j\in I$, and
therefore it solves the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$ in
one round. It follows that $\tau\in\Delta^{\prime}_{\epsilon}(\sigma)$.

The two maps $\Delta^{\prime}_{\epsilon}$ and $\Delta_{2\epsilon}$ are
therefore identical, which completes the proof of Claim 4. ∎

We complete the proof of Theorem 4 by the same reasoning as in the proof of
Corollary 3, but using Theorem 1 and Claim 4. Let us fix $\epsilon>0$ and
$n\geq 3$. Consider an algorithm solving $\epsilon$-approximate agreement in
$t$ rounds—this algorithm also solves the liberal version of
$\epsilon$-approximate agreement in $t$ rounds. By Theorem 1 and Claim 4,
there is an algorithm solving the liberal version of $(2\epsilon)$-approximate
agreement in $t-1$ rounds, and repeating this argument for $t$ times implies
an algorithm solving the liberal version of $(2^{t}\epsilon)$-approximate
agreement algorithm in $0$ rounds. Now, note that Claim 1 still holds, since
the test&set object is not used in a zero round algorithm, thus we have
$2^{t}\epsilon\geq 1$, which immediately implies the lower bound. ∎

###  5.3. Approximate Agreement in the Wait-Free IIS Model with Binary
Consensus

Figure 7. The 1-round protocol complex using binary consensus when the black
process calls consensus with input 0, and the other two processes call
consensus with input 1.

In this section, we consider again the approximate agreement task, but in the
model of iterated immediate snapshot augmented with binary consensus. Clearly,
in this model, $\epsilon$-approximate agreement is solvable for every
$\epsilon$ whenever $n=2$. Figure 7 displays the $1$-round protocol complex
$\mathcal{P}^{(1)}(\sigma)$ for a $2$-dimensional simplex $\sigma$. Here, the
vertices of the input simplex $\sigma$ are labeled with the values with which
the processes call the binary consensus object, and the vertices of the
protocol complex $\mathcal{P}^{(1)}(\sigma)$ are labeled with the output
values of this object. The protocol complex $\mathcal{P}^{(1)}(\sigma)$ can
thus be viewed as two copies of the chromatic subdivision of $\sigma$, one for
which consensus is $0$, and the other for which consensus is $1$. However, in
each copy, some simplices are removed, depending of the input given to the
consensus object. For instance, in the figure, the black process calls the
object with input $0$, so it must also output $0$ in a solo execution, and the
vertex where it outputs $1$ in a solo execution is removed. Similarly, the
white and red processes call the object with input $1$, so all executions in
which only these processes participate result in both processes outputting
$1$.

We are aware of two techniques for solving approximate agreement using binary
consensus, both consist in agreeing on a value one bit at a time. One
technique is solving (exact) consensus in $\lceil\log_{2}n\rceil$ rounds, by
agreeing on the ID of one of the participating processes, and then deciding on
its input. The other techniques takes $\lceil\log_{2}1/\epsilon\rceil$ rounds,
and goes as follows. At round $r$, each process writes its current value, then
evokes the binary consensus object with the $r$-th bit of its current value
(starting from the most significant bit), and, finally, updates its current
value to one of the proposed values whose $r$-th bit is equal to the output of
the consensus object. Note that the call to the binary consensus object in the
first type of algorithms depends only on the process ID, and not on its input
or current value. Instead, in the second type of algorithms, the call to the
binary consensus object depends solely on the value and not on the process ID.
In this section, we give a lower bound that applies to algorithms of the first
type, i.e., algorithms where the call of a process to the binary consensus
object depends solely on its ID and round number.

###### Theorem 5.

The number of rounds required by $n\geq 3$ processes for solving the
$\epsilon$-approximate agreement task in the wait-free IIS model augmented
with a binary consensus object called with inputs depending only on the
process IDs and round numbers is at least
$\min\\{\lceil\log_{2}1/\epsilon\rceil,\lceil\log_{2}n\rceil-1\\}$.

###### Proof.

Let $n\geq 3$. Let $M$ be the iterated immediate snapshot model augmented with
a binary consensus object, with the restriction that the input value used by
every process $i\in[n]$ to call the binary consensus object at each round
$r\geq 1$ may depend only on $i$ and $r$. Under these assumptions, we can
strengthen the statement of Theorem 1 as follows. Let $\beta:[n]\to\\{0,1\\}$
be a function. We define the closure of a task
$\Pi=(\mathcal{I},\mathcal{O},\Delta)$ with respect to $\beta$, denoted by
$\mbox{\footnotesize\sf CL}_{M}(\Pi|\beta)$, as the task
$\Pi=(\mathcal{I},\mathcal{O}^{\prime},\Delta^{\prime})$ where, for every
simplex $\sigma\in\mathcal{I}$, and for every chromatic set $\tau\subseteq
V(\Delta(\sigma))$, we set $\tau\in\Delta^{\prime}(\sigma)$ if and only if the
local task $\Pi_{\tau,\sigma}=(\tau,\Delta(\sigma),\Delta_{\tau,\sigma})$ is
solvable in one round by an algorithm in which, for every $i\in[n]$, process
$i$ calls the binary consensus object with input $\beta(i)$. The following
claim is an analog of Theorem 1 for the closure task with respect to functions
$\beta$.

###### Claim 5.

For every $t\geq 1$, if a task $\Pi$ is solvable in $t$ rounds in the model
$M$, then there exists a function $\beta:[n]\to\\{0,1\\}$ such that
$\mbox{\footnotesize\sf CL}_{M}(\Pi|\beta)$ is solvable in $t-1$ rounds in
$M$.

###### Proof of claim.

The proof is identical to the proof of Theorem 1, by noticing that, during its
$t$-th round, every process $i$ running the algorithm calls the binary
consensus object with input $\alpha(i,t)$, which is independent of the view
and depends only on the process ID and the round. The desired function $\beta$
is therefore merely defined as $\beta(i)=\alpha(i,t)$ for every $i\in[n]$. ∎

By fixing the function $\beta$ used by the processes for calling the binary
consensus object, we will be able to show that if the original task is
$\epsilon$-approximate agreement, then the closure $\mbox{\footnotesize\sf
CL}_{M}(\Pi|\beta)$ with respect to $\beta$ is actually
$(2\epsilon)$-approximate agreement whenever only some (large) group of
processes participate. More specifically, let $S$ be the largest of the two
sets $\beta^{-1}(0)$ and $\beta^{-1}(1)$, with $S=\beta^{-1}(0)$ if they are
of equal sizes, and note that $|S|\geq n/2$. Intuitively, when only the
processes in $S$ participate, they take no benefit of the consensus object, to
which they all input the same value $a$, and from which they all get the same
output $b=a$. Hence, when only processes in $S$ participate the closure of
$\epsilon$-approximate agreement with respect to $\beta$ is
$(2\epsilon)$-approximate agreement, as is the case without binary consensus
object. We then repeat the same argument on $S$, by identifying a set
$S^{\prime}\subseteq S$ that may result from another function,
$\beta^{\prime}$, of size at least $n/4$, such that, whenever only the
processes in $S^{\prime}$ participate, the closure with respect to
$\beta^{\prime}$ of the closure of $\epsilon$-approximate agreement with
respect to $\beta$ is $(4\epsilon)$-approximate agreement. At each iteration
of this reasoning, we halve the number of processes, and double the precision
parameter of the approximate agreement task, until either the number of
processes becomes very small or the precision parameter becomes very large, in
which cases the task becomes easier. Therefore, the number of iterations of
this reasoning is roughly $\min\\{\log_{2}1/\epsilon,\log_{2}n\\}$. The exact
figures are slightly more complicate because, for two processes,
$\epsilon$-approximate agreement does not require at least
$\lceil\log_{2}1/\epsilon\rceil$ rounds but $\lceil\log_{3}1/\epsilon\rceil$
rounds in absence of a binary consensus object, and just a single round with
such an object.

The following claim is at the core of the proof.

###### Claim 6.

Let $\Pi=(\mathcal{I},\mathcal{O},\Delta)$ be the liberal version of
$\epsilon$-approximate agreement task on a set $S\subseteq[n]$ of $|S|\geq 5$
processes, and let $\beta:S\to\\{0,1\\}$ be any function. Then there is a
subset $S^{\prime}\subseteq S$ of processes, with $|S^{\prime}|\geq|S|/2$,
such that $\mbox{\footnotesize\sf CL}_{M}(\Pi|\beta)$ is the liberal version
of $(2\epsilon)$-approximate agreement task whenever only the processes of
$S^{\prime}$ participate.

###### Proof of claim.

Let $S^{\prime}\subseteq S$ be the largest of the sets $\beta^{-1}(0)$ and
$\beta^{-1}(1)$ (and $\beta^{-1}(0)$ in case of equal sizes). We henceforth
assume, without lost of generality, that $S^{\prime}=\beta^{-1}(0)$. Note that
$|S^{\prime}|\geq 3$, as $|S|\geq 5$. Let
$\Pi_{\epsilon}=(\mathcal{I},\mathcal{O}_{\epsilon},\Delta_{\epsilon})$ be the
liberal version of $\epsilon$-approximate agreement task on $S$, and let
$\mbox{\footnotesize\sf
CL}_{M}(\Pi_{\epsilon}|\beta)=(\mathcal{I},\mathcal{O}^{\prime}_{\epsilon},\Delta^{\prime}_{\epsilon})$.
Let us denote the liberal version of $(2\epsilon)$-approximate agreement on
$S$ by
$\Pi_{2\epsilon}=(\mathcal{I},\mathcal{O}_{2\epsilon},\Delta_{2\epsilon})$. We
want to show that, restricted to the processes in $S^{\prime}$, the two tasks
$\Pi_{2\epsilon}$ and $\mbox{\footnotesize\sf CL}_{M}(\Pi_{\epsilon}|\beta)$
are identical. Formally, we want to show that, for every
$\sigma\in\mathcal{I}$ with $\mbox{\sc{id}}(\sigma)\subseteq S^{\prime}$,
$\Delta^{\prime}_{\epsilon}(\sigma)=\Delta_{2\epsilon}(\sigma)$. If
$\sigma=\\{v\\}$ is a single vertex, then
$\Delta_{2\epsilon}(\\{v\\})=\\{v\\}$, and
$\Delta^{\prime}_{\epsilon}(\\{v\\})=\\{v\\}$, and thus
$\Delta^{\prime}_{\epsilon}(\sigma)=\Delta_{2\epsilon}(\sigma)$ as desired. If
$|\sigma|=2$ then the fact that the liberal version of the tasks does not
depend on $\epsilon$ makes the maps equal:
$\Delta^{\prime}_{\epsilon}(\sigma)=\\{(j,y_{j})\mid j\in
I,\;\min\\{x_{i}:i\in I\\}\leq y_{j}\leq\max\\{x_{i}:i\in
I\\}\\}=\Delta_{2\epsilon}(\sigma)$. Let us now consider an input simplex
$\sigma=\\{(i,x_{i})\mid i\in I\\}\in\mathcal{I}$, for some set $I\subseteq
S^{\prime}$, with $|I|\geq 3$.

First, we show that
$\Delta_{\epsilon}^{\prime}(\sigma)\subseteq\Delta_{2\epsilon}(\sigma)$. Let
$\tau=\\{(i,y_{i})\mid i\in I\\}\in\Delta_{\epsilon}^{\prime}(\sigma)$. We
want to show that $\tau\in\Delta_{2\epsilon}(\sigma)$, i.e., (1)
$\min\\{x_{i}:i\in I\\}\leq y_{i}\leq\max\\{x_{i}:i\in I\\}$ for all $i\in I$,
and (2) $|y_{i}-y_{j}|\leq 2\epsilon$ for all $i,j\in I$. Since
$\tau\in\Delta_{\epsilon}^{\prime}(\sigma)$, the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$ is
solvable in one round, using an algorithm in which each process $i\in I$ calls
the binary consensus object with input $\beta(i)=0$. Let
$f:\mathcal{P}^{(1)}(\tau)\to\Delta_{\epsilon}(\sigma)$ be a simplicial map
solving the local task $\Pi_{\tau,\sigma}$ where $f:\mathcal{P}^{(1)}(\tau)$
is the 1-round protocol complex in model $M$ starting from $\tau$ with input 0
to the binary consensus object. Since $\tau\subseteq
V(\Delta_{\epsilon}(\sigma))$, property (1) holds. To check property (2), note
that since all processes in $I\subseteq S^{\prime}$ call the binary consensus
object with the same input value 0, they necessarily all get the same value 0
as output. This allows us to follow arguments similar to the ones used in the
proof of Claim 3. Let us consider three processes $i,j,k\in I$, and let us
define $\gamma$ by $f(k,(0,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\}))=(k,\gamma),$
where the 0 in this definition is the output of binary consensus at process
$k$. Since $f$ solves the local task $\Pi_{\tau,\sigma}$, we have
$f(i,(0,\\{(i,y_{i})\\}))=(i,y_{i})\;\mbox{and}\;f(j,(0,\\{(j,y_{j})\\}))=(j,y_{j}),$
where, again, the $0$ values in these equalities are the outputs of binary
consensus at processes $i$ and $j$, respectively. Since $f$ solves the local
task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$,
we have

$\big{\\{}f(i,(0,\\{(i,y_{i})\\})),\;f(k,(0,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\}))\big{\\}}\in\Delta_{\epsilon}(\sigma)$

and

$\big{\\{}f(j,(0,\\{(j,y_{j})\\})),\;f(k,(0,\\{(i,y_{i}),(j,y_{j}),(k,y_{k})\\}))\big{\\}}\in\Delta_{\epsilon}(\sigma).$

It follows that $|y_{i}-y_{j}|\leq|y_{j}-\gamma|+|\gamma-y_{i}|\leq
2\epsilon$, and therefore $\tau\in\Delta_{2\epsilon}(\sigma)$.

Conversely, we show that
$\Delta_{2\epsilon}(\sigma)\subseteq\Delta_{\epsilon}^{\prime}(\sigma)$. Let
$\tau=\\{(i,y_{i})\mid i\in I\\}\in\Delta_{2\epsilon}(\sigma)$. We show that
the local task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$ is
solvable in one round, using an algorithm in which each process $i\in I$ calls
the binary consensus object with input $\beta(i)=0$. Since $I\subseteq
S^{\prime}$, the output of the object is necessarily $0$ at every process
$i\in I$. Let $f:\mathcal{P}^{(1)}(\tau)\to\Delta_{\epsilon}(\sigma)$ be as
follows. For every $i\in I$, and every set $J\subseteq I$ satisfying $i\in J$,
we set

$f(i,(0,\\{y_{j}:j\in J\\}))=\Big{(}i,\min\big{\\{}\max\\{y_{j}:j\in
J\\},\min\\{y_{j}:j\in J\\}+\epsilon\big{\\}}\Big{)}.$

This map $f$ solves $\epsilon$-approximate agreement whenever
$|y_{i}-y_{j}|\leq 2\epsilon$ for any $i,j\in I$, and therefore it solves the
local task
$\Pi_{\tau,\sigma}=(\tau,\Delta_{\epsilon}(\sigma),{\Delta}_{\tau,\sigma})$ in
one round. It follows that $\tau\in\Delta^{\prime}_{\epsilon}(\sigma)$. This
completes the proof of Claim 6. ∎

We now have all the ingredients for establishing the lower bound. For this
purpose, let
$t=\min\\{\lceil\log_{2}n\rceil-1,\lceil\log_{2}1/\epsilon\rceil\\}$, and let
us assume, for the purpose of contradiction, that there exists an algorithm
solving the liberal version of $\epsilon$-approximate agreement in $t-1$
rounds. By Claims 5 and 6, this implies the existence of a $(t-2)$-round
algorithm solving the liberal version of $(2\epsilon)$-approximate agreement
among a set $S_{1}\subseteq[n]$ of processes, with $|S_{1}|\geq n/2$. By
iterating the application of Claims 5 and 6, we eventually get a 0-round
algorithm solving the liberal version of $(2^{t-1}\epsilon)$-approximate
agreement among a set $S_{t-1}\subseteq[n]$ of processes, with $|S_{t-1}|\geq
n/2^{t-1}$. Since $t\leq\lceil\log_{2}n\rceil-1$, using the fact that
$\lceil\log_{2}n\rceil<\log_{2}n+1$, we get
$|S_{t-1}|>\frac{n}{2^{\log_{2}n-1}}$, and thus $|S_{t-1}|\geq 3$. Also, since
$t\leq\lceil\log_{2}1/\epsilon\rceil$, using similarly the fact that,
$\lceil\log_{2}1/\epsilon\rceil<\log_{2}1/\epsilon+1$, we get that
$2^{t-1}\epsilon<1$. Therefore, we get a 0-round algorithm solving the liberal
version of $\epsilon^{\prime}$-approximate agreement among a set of at least
three processes, where $\epsilon^{\prime}<1$. This is a contradiction with
Claim 1, which still holds in the context of the theorem since, in $0$ rounds,
the binary consensus object is not used. Therefore, the liberal version of
$\epsilon$-approximate agreement requires at least $t$ rounds to be solved,
and so does the (standard version of) $\epsilon$-approximate agreement. ∎

##  6\. Conclusion

Our results open many interesting questions. Our asynchronous speedup theorem
is inspired by an analogous speedup technique (Balliu et al., 2019; Brandt,
2019) for the LOCAL model, and we believe that the two forms of speedup
theorems shed light on the differences between asynchronous computation and
computation in the LOCAL model. In particular, it seems that while in the
LOCAL model it is possible to state a generic “if and only if” form of a
speedup theorem, this is not the case for asynchronous computation in the
wait-free model.

We have established our speedup theorem in iterated models. It would be
interesting to extend it to non-iterated models, in which a register can be
used multiple times. This seems especially interesting, since while the
iterated and the non-iterated models are known to be equivalent with respect
to task solvability (Borowsky and Gafni, 1997; Gafni and Rajsbaum, 2010;
Bouzid et al., 2014; Imbs et al., 2015) (even when enriched with some more
powerful objects), they are not known to be equivalent in terms of time
complexity. Moreover, our speedup theorem assumes models allowing processes to
run solo, as in standard wait-free models, and it would be interesting to
study extensions to affine models (Kuznetsov et al., 2018) without this
property, such as $t$-resilient models for $t<n-1$.

We focused on some objects of consensus-number $2$, such as test&set, and
showed that they are useless for solving approximate agreement faster. We
would be interested in extending this result to every consensus-number-2
object. However, we showed that even objects with consensus number $\infty$,
such as binary consensus, are not useful for solving $\epsilon$-approximate
agreement (at least when $n\geq 1/\epsilon$) faster, so perhaps the answer is
independent of the consensus hierarchy. And finally, it would be interesting
to use the speedup theorem for problems other than consensus and approximate
agreement.

## References

  * (1)
  * Aspnes and Herlihy (1990) J. Aspnes and M. Herlihy. 1990.  Wait-Free Data Structures in the Asynchronous PRAM Model. In _2nd ACM Symposium on Parallel Algorithms and Architectures (SPAA)_ (Island of Crete, Greece). 340–349.  https://doi.org/10.1145/97444.97701
  * Attiya et al. (2019) Hagit Attiya, Armando Castañeda, Maurice Herlihy, and Ami Paz. 2019.  Bounds on the Step and Namespace Complexity of Renaming.  _SIAM J. Comput._ 48, 1 (2019), 1–32.
  * Attiya and Ellen (2014) Hagit Attiya and Faith Ellen. 2014.  _Impossibility Results for Distributed Computing_.  Morgan & Claypool Publishers.  https://doi.org/10.2200/S00551ED1V01Y201311DCT012
  * Attiya and Rajsbaum (2020) Hagit Attiya and Sergio Rajsbaum. 2020.  Indistinguishability.  _Commun. ACM_ 63, 5 (2020), 90–99.  https://doi.org/10.1145/3376902
  * Attiya and Welch (2004) Hagit Attiya and Jennifer Welch. 2004.  _Distributed Computing: Fundamentals, Simulations and Advanced Topics_.  John Wiley & Sons, Hoboken, NJ, USA.
  * Balliu et al. (2019) Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela. 2019\.  Lower Bounds for Maximal Matchings and Maximal Independent Sets. In _60th IEEE Symposium on Foundations of Computer Science (FOCS)_. 481–497.  https://doi.org/10.1109/FOCS.2019.00037
  * Bastide and Fraigniaud (2021) Paul Bastide and Pierre Fraigniaud. 2021.  Brief Annoucement: On Extending Brandt’s Speedup Theorem from LOCAL to Round-Based Full-Information Models. In _35th International Symposium on Distributed Computing (DISC)_ _(LIPIcs, Vol. 209)_. Schloss Dagstuhl, 47:1–47:4.  https://doi.org/10.4230/LIPIcs.DISC.2021.47
  * Benavides and Rajsbaum (2018) Fernando Benavides and Sergio Rajsbaum. 2018.  Collapsibility of read/write models using discrete morse theory.  _J. Appl. Comput. Topol._ 1, 3-4 (2018), 365–396.  https://doi.org/10.1007/s41468-018-0011-7
  * Borowsky and Gafni (1993) Elizabeth Borowsky and Eli Gafni. 1993.  Generalized FLP impossibility result for $t$-resilient asynchronous computations. In _25 ACM Symposium on Theory of Computing (STOC)_. 91–100.  https://doi.org/10.1145/167088.167119
  * Borowsky and Gafni (1997) Elizabeth Borowsky and Eli Gafni. 1997.  A Simple Algorithmically Reasoned Characterization of Wait-Free Computations (Extended Abstract). In _16th ACM Symposium on Principles of Distributed Computing (PODC)_. 189–198.  https://doi.org/10.1145/259380.259439
  * Bouzid et al. (2014) Zohir Bouzid, Eli Gafni, and Petr Kuznetsov. 2014.  Strong Equivalence Relations for Iterated Models. In _18th International Conference on Principles of Distributed Systems (OPODIS)_ _(LNCS 8878)_. Springer, 139–154.  https://doi.org/10.1007/978-3-319-14472-6_10
  * Brandt (2019) Sebastian Brandt. 2019\.  An Automatic Speedup Theorem for Distributed Problems. In _38th ACM Symposium on Principles of Distributed Computing (PODC)_. 379–388.  https://doi.org/10.1145/3293611.3331611
  * Castañeda et al. (2021) Armando Castañeda, Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum, Matthieu Roy, and Corentin Travers. 2021.  A topological perspective on distributed network algorithms.  _Theor. Comput. Sci._ 849 (2021), 121–137.  https://doi.org/10.1016/j.tcs.2020.10.012
  * Chandra et al. (2005) Tushar Chandra, Vassos Hadzilacos, Prasad Jayanti, and Sam Toueg. 2005.  Generalized Irreducibility of Consensus and the Equivalence of t-Resilient and Wait-Free Implementations of Consensus.  _SIAM J. Comput._ 34, 2 (2005), 333–357.  https://doi.org/10.1137/S0097539798344367 arXiv:https://doi.org/10.1137/S0097539798344367
  * Dolev et al. (1986) Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. 1986\.  Reaching Approximate Agreement in the Presence of Faults.  _J. ACM_ 33, 3 (may 1986), 499?516.  https://doi.org/10.1145/5925.5931
  * Ellen et al. (2018) Faith Ellen, Rati Gelashvili, and Leqi Zhu. 2018\.  Revisionist Simulations: A New Approach to Proving Space Lower Bounds. In _Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC_. ACM, 61–70.
  * Fich and Ruppert (2003) Faith E. Fich and Eric Ruppert. 2003.  Hundreds of impossibility results for distributed computing.  _Distributed Comput._ 16, 2-3 (2003), 121–163.  https://doi.org/10.1007/s00446-003-0091-y
  * Fischer et al. (1985) Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. 1985\.  Impossibility of Distributed Consensus with One Faulty Process.  _J. ACM_ 32, 2 (1985), 374–382.  https://doi.org/10.1145/3149.214121
  * Fraigniaud and Paz (2020) Pierre Fraigniaud and Ami Paz. 2020.  The Topology of Local Computing in Networks. In _47th International Colloquium on Automata, Languages, and Programming (ICALP)_ _(LIPIcs, Vol. 168)_. Schloss Dagstuhl, 128:1–128:18.  https://doi.org/10.4230/LIPIcs.ICALP.2020.128
  * Függer et al. (2021) Matthias Függer, Thomas Nowak, and Manfred Schwarz. 2021\.  Tight Bounds for Asymptotic and Approximate Consensus.  _J. ACM_ 68, 6, Article 46 (oct 2021), 35 pages.  https://doi.org/10.1145/3485242
  * Gafni and Guerraoui (2011) Eli Gafni and Rachid Guerraoui. 2011.  Generalized Universality. In _Proceedings of the 22nd International Conference on Concurrency Theory_ (Aachen, Germany) _(CONCUR’11)_. Springer-Verlag, Berlin, Heidelberg, 17–27.
  * Gafni and Rajsbaum (2010) Eli Gafni and Sergio Rajsbaum. 2010.  Distributed Programming with Tasks. In _14th International Conference on Principles of Distributed Systems (OPODIS)_ _(LNCS 6490)_. Springer, 205–218.  https://doi.org/10.1007/978-3-642-17653-1_17
  * Herlihy (1991) Maurice Herlihy. 1991\.  Wait-Free Synchronization.  _ACM Trans. Program. Lang. Syst._ 13, 1 (1991), 124–149.
  * Herlihy et al. (2013) Maurice Herlihy, Dmitry N. Kozlov, and Sergio Rajsbaum. 2013\.  _Distributed Computing Through Combinatorial Topology_.  Morgan Kaufmann.
  * Herlihy and Rajsbaum (1995) Maurice Herlihy and Sergio Rajsbaum. 1995.  Algebraic Topology and Distributed Computing: A Primer.  In _Computer Science Today: Recent Trends and Developments_. LNCS, Vol. 1000. Springer, 203–217.  https://doi.org/10.1007/BFb0015245
  * Herlihy et al. (2017) Maurice Herlihy, Sergio Rajsbaum, Michel Raynal, and Julien Stainer. 2017.  From wait-free to arbitrary concurrent solo executions in colorless distributed computing.  _Theoretical Computer Science_ 683 (2017), 1–21.  https://doi.org/10.1016/j.tcs.2017.04.007
  * Herlihy and Shavit (1999) Maurice Herlihy and Nir Shavit. 1999.  The topological structure of asynchronous computability.  _J. ACM_ 46, 6 (1999), 858–923.  https://doi.org/10.1145/331524.331529
  * Hoest and Shavit (2006) Gunnar Hoest and Nir Shavit. 2006.  Toward a Topological Characterization of Asynchronous Complexity.  _SIAM J. Comput._ 36, 2 (2006), 457–497.  https://doi.org/10.1137/S0097539701397412
  * Imbs et al. (2015) Damien Imbs, Sergio Rajsbaum, and Adrián Valle. 2015\.  Untangling Partial Agreement: Iterated x-consensus Simulations. In _17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)_ _(LNCS 9212)_. Springer, 139–155.  https://doi.org/10.1007/978-3-319-21741-3_10
  * Kozlov (2015) Dmitry Kozlov. 2015\.  Topology of the view complex.  _Homology Homotopy Appl._ 17, 1 (2015), 307–319.
  * Kuznetsov et al. (2018) Petr Kuznetsov, Thibault Rieutord, and Yuan He. 2018.  An Asynchronous Computability Theorem for Fair Adversaries. In _Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing_ (Egham, United Kingdom) _(PODC ’18)_. Association for Computing Machinery, New York, NY, USA, 387?396.  https://doi.org/10.1145/3212734.3212765
  * Lynch (1989) Nancy A. Lynch. 1989\.  A Hundred Impossibility Proofs for Distributed Computing. In _8th ACM Symposium on Principles of Distributed Computing (PODC)_. 1–28.  https://doi.org/10.1145/72981.72982
  * Moses and Rajsbaum (2002) Yoram Moses and Sergio Rajsbaum. 2002.  A Layered Analysis of Consensus.  _SIAM J. Comput._ 31, 4 (apr 2002), 989?1021.  https://doi.org/10.1137/S0097539799364006
  * Mostefaoui et al. (2000) Achour Mostefaoui, Michel Raynal, and Frédéric Tronel. 2000\.  From Binary Consensus to Multivalued Consensus in Asynchronous Message-Passing Systems.  _Inf. Process. Lett._ 73, 5-6 (2000), 207–212.  https://doi.org/10.1016/S0020-0190(00)00027-2
  * Rajsbaum (2010) Sergio Rajsbaum. 2010\.  Iterated Shared Memory Models. In _LATIN 2010: Theoretical Informatics_ , Alejandro López-Ortiz (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 407–416.
  * Raynal (2018) Michel Raynal. 2018\.  _Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach_.  Springer.  https://doi.org/10.1007/978-3-319-94141-7
  * Saks and Zaharoglou (1993) Michael E. Saks and Fotios Zaharoglou. 1993.  Wait-free $k$-set agreement is impossible: the topology of public knowledge. In _25th ACM Symposium on Theory of Computing (STOC)_. 101–110.  https://doi.org/10.1145/167088.167122

A P P E N D I X

##  Appendix A Model

###  A.1. Element of Algebraic Topology

Recall that a _complex_ is a collection $\mathcal{K}$ of non-empty sets,
closed under inclusion, i.e., if $\sigma\in\mathcal{K}$ then, for every non-
empty set $\sigma^{\prime}\subseteq\sigma$, $\sigma^{\prime}\in\mathcal{K}$.
Every set in $\mathcal{K}$ is called a _simplex_. A subset of a simplex is
called a _face_ , and a _facet_ of $\mathcal{K}$ is a face that is maximal for
inclusion in $\mathcal{K}$. The _dimension_ of a simplex $\sigma$ is
$|\sigma|-1$, where $|\sigma|$ denotes the cardinality of $\sigma$. The
dimension of a complex is the maximal dimension of its facets. A complex in
which all facets are of the same dimension is called _pure_. The _vertices_ of
$\mathcal{K}$ are all simplices with a single element (i.e., of dimension 0).
The set of vertices of a complex $\mathcal{K}$ are denoted by
$V(\mathcal{K})$.

All complexes in this paper are _chromatic_ , i.e., every vertex is a pair
$v=(i,x)$ where $i\in[n]=\\{1,\dots,n\\}$ for some $n\geq 1$ is the _color_ of
$v$, and $x$ is some value (e.g., an input value, an output value, or some
value corresponding to a set of data acquired after some computation).
Moreover, in a chromatic complex, a “color” $i$ must appear at most once in
every simplex, that is, a simplex is of the form $\sigma=\\{(i,v_{i}):i\in
I\\}$ for some non-empty set $I\subseteq[n]$. Appendix B contains figures
depicting some chromatic simplicial complexes; these specific simplices are
discussed later.

A _simplicial map_ from a complex $\mathcal{K}$ to a complex
$\mathcal{K}^{\prime}$ is a map $f:V(\mathcal{K})\to V(\mathcal{K}^{\prime})$
preserving simplices, that is, for every simplex $\sigma$, the set $f(\sigma)$
is a simplex of $\mathcal{K}^{\prime}$. All simplicial maps considered in this
paper are chromatic, that is, they preserve the colors of the vertices, i.e.,
for every $(i,x)\in V(\mathcal{K})$, $f(i,x)=(i,y)\in
V(\mathcal{K}^{\prime})$. So, given a chromatic simplicial map from a
chromatic complex $\mathcal{K}$ to a chromatic complex $\mathcal{K}^{\prime}$,
for every $\sigma=\\{(i,x_{i}):i\in I\\}\in\mathcal{K}$, the set
$f(\sigma)=\\{f(i,x_{i}):i\in I\\}$ is a chromatic simplex of $\mathcal{K}$ on
the same set of colors. Since simplicial maps sends simplices to simplices, we
often write $f:\mathcal{K}\to\mathcal{K}^{\prime}$ even if $f$ is actually
defined on vertices.

A _carrier map_ from a chromatic complex $\mathcal{K}$ to a chromatic complex
$\mathcal{K}^{\prime}$ is a map $\Delta:\mathcal{K}\to
2^{\mathcal{K}^{\prime}}$ which maps every simplex $\sigma\in\mathcal{K}$ to a
pure sub-complex of $\mathcal{K}^{\prime}$ with same dimension and same colors
as $\sigma$ such that, for every $\sigma^{\prime}\subseteq\sigma$,
$\Delta(\sigma^{\prime})\subseteq\Delta(\sigma)$, i.e.,
$\Delta(\sigma^{\prime})$ is a subcomplex of $\Delta(\sigma)$.

Any simplex $\sigma$ of a (chromatic) complex $\mathcal{K}$ can also be viewed
as a complex $\bar{\sigma}$ whose simplices are all the faces of $\sigma$. To
avoid overloading the notations, we will omit the bar over $\sigma$ when it is
clear from the context whether we consider $\sigma$ as a simplex or as a
complex. The same holds for a collection of simplices of a (chromatic) complex
$\mathcal{K}$.

##### Notations.

Let $\sigma=\\{(i,x_{i}):i\in I\\}$ be a simplex. We denote by
$\mbox{\sc{id}}(\sigma)$ the set of colors in $\sigma$, i.e.,
$\mbox{\sc{id}}(\sigma)=I$. Indeed, in the following, the color of a vertex is
actually the _identity_ of a process. For every non-empty set $J\subseteq I$,
we denote by $\mathsf{proj}_{J}(\sigma)$ the simplex $\\{(i,x_{i}):i\in J\\}$,
i.e., $\mbox{\sc{id}}(\mathsf{proj}_{J}(\sigma))=J$. That is,
$\mathsf{proj}_{J}(\sigma)$ is the _projection_ of $\sigma$ resulting from
considering only vertices with colors in $J$.

###  A.2. Tasks

We consider distributed systems with $n\geq 2$ processes, labeled by distinct
integers from 1 to $n$. Every process $i$ initially know its identity $i$ as
well as the total number $n$ of processes in the system. A _task_ for $n$
processes is a triple $(\mathcal{I},\mathcal{O},\Delta)$ where $\mathcal{I}$
and $\mathcal{O}$ are $(n-1)$-dimensional complexes, respectively called
_input_ and _output_ complexes, and $\Delta:\mathcal{I}\to 2^{\mathcal{O}}$ is
an input-output specification. Every simplex $\sigma=\\{(i,x_{i}):i\in I\\}$
of $\mathcal{I}$ defines a legal input state corresponding to the scenario in
which, for every $i\in I$, process $i$ starts with input value $x_{i}$.
Similarly, every simplex $\tau={\\{(i,y_{i}):i\in I\\}}$ of $\mathcal{O}$
defines a legal output state corresponding to the scenario in which, for every
$i\in I$, process $i$ outputs the value $y_{i}$. The map $\Delta$ is an input-
output relation specifying, for every input state $\sigma\in\mathcal{I}$, the
set of output states $\tau\in\mathcal{O}$ with
$\mbox{\sc{id}}(\tau)=\mbox{\sc{id}}(\sigma)$ that are legal with respect to
$\sigma$. That is, assuming that only the processes in
$\mbox{\sc{id}}(\sigma)$ participate to the computation (the set of
participating processes is not known a priori to the processes in $\sigma$),
there processes are allow to output any simplex $\tau\in\Delta(\sigma)$. It is
usually assumed that $\Delta$ is a carrier map, but in this paper we do not
enforce this requirement into the definition.

###  A.3. Computational Model

We consider asynchronous computing in the standard _read-write shared memory_
distributed computing model (Attiya and Welch, 2004), focusing on iterated
models (Rajsbaum, 2010), following the topology approach to distributed
computing (Herlihy et al., 2013).

####  A.3.1. Read-Write Shared Memory

A _process_ is a deterministic (infinite) state machine. We consider a
collection of $n\geq 2$ _processes_ that exchange information by accessing to
a shared memory. Processes are labeled from 1 to $n$, and process $i$ is aware
of its label, called _identifier_ (ID), as well as of the size $n$ of the
system. The shared memory has $n$ distinct single-writer multiple-reader
(SWMR) _registers_ $R[1],\dots,R[n]$. Each process $i\in[n]$ can store data in
the shared memory by _writing_ in its register $R[i]$, and no other processes
can write in $R[i]$. On the other hand, for every $i\in[n]$, $R[i]$ can be
_read_ by any process $j\in[n]$.

Since we are focussing on lower bounds, we assume no limits on the
computational power of the processes, and on the size of their private
memories. Similarly, we assume no limits to the size of the registers in the
shared memory. In particular, we assume that no information is ever lost once
written in the shared memory. Finally, we assume no limits on the amount of
information that can be transferred from and to the memory by the processes.
In particular, when a process writes in its register, we assume that it writes
the whole content of its private memory. Similarly when it reads a register,
we assume that it reads the whole content of that register. These assumptions
are referred to as the _full-information_ model (Herlihy et al., 2013).

Also, since our objective is the design of lower bounds, we assume that each
communication, i.e., writing to, or reading from a register, is _atomic_.
Similarly, each sequence of internal computation performed by a process
between two successive accesses to the shared memory is supposed to be atomic.
However, the overall system is supposed to be _asynchronous_. That is, the
time at which each atomic operation of a process is executed is arbitrary and
unpredictable, apart from the fact that the atomic operations executed by a
same process are executed in order.

####  A.3.2. Iterated Models

We adopt a standard approach for designing robust algorithms in shared-memory
systems involving processes subject to crash failures, by focussing on
algorithms with a generic form, using the _collect_ instruction.

##### Collect:

For every $i\in[n]$, the _collect_ instruction performed by process $i$
results in this process reading all registers $R[j]$ sequentially, for
$j=1,\dots,n$, in arbitrary order.

Such a generic form of algorithm is Algorithm 1, for the _iterated_ model, in
which the shared-memory is organized in arrays $M_{r}$, $r\geq 1$, of $n$ SWMR
registers (one per process) and each round $r$ of the protocol is executed on
a the array $M_{r}$. At each round, each process $i$ updates its so-called
_view_ $V_{i}$ by collecting the views of the other processes. Initially, the
view $V_{i}$ of process $i$ is reduced to its own input $x_{i}$. Then, a
sequence of $t$ rounds are performed, for some $t\geq 0$, where a round is
defined as a sequence of two consecutive write and collect operations. At the
end of round 1, the view $V_{i}$ of process $i$ is a set of pairs $(j,x_{j})$.
It must be the case that $(i,x_{i})\in V_{i}$ as the collect instruction is
performed after the write instruction. For $j\neq i$, it may or may not be the
case that $(j,x_{j})\in V_{i}$ depending on whether the write of process $j$
in $M_{1}[j]$ was executed before or after the read of process $i$ in
$M_{1}[j]$ performed during the collect by process $i$ of all the registers’
content at round 1. After round 2, the view $V_{i}$ of process $i$ is a set of
sets of inputs, whose content depends on the input values to the processes,
and on the interleaving of the reads and writes performed by the processes
during rounds 1 and 2. And so on, until process $i$ obtains its final view
$V_{i}$ after $t$ rounds. At this point, process $i$ applies some function $f$
on this view, which results in the output $y_{i}$ decided by process $i$. The
function $f$ is specific of the algorithm, and distinct $t$-round algorithms
differ solely in the function $f$ applied to the view after $t$ rounds of
communication.

Interestingly, the generic form of round-based algorithms assumes that all
internal computations are postponed to the very end of the execution. This is
without loss of generality because, as the model is full-information, any
algorithm in which internal computations are inserted between write and read
operations can be simulated by an algorithm satisfying the generic form. A
generic algorithm can tolerate an arbitrary large number (up to $n-1$) of
crash failures, as any correct process terminates after $t$ rounds,
independently from the number of processes that crash.

####  A.3.3. Snapshot and Immediate Snapshot

Note that while the read operation is supposed to be atomic, the collect
operation is not atomic, for it is just a sequence of $n$ successive read
operations, one in each register. So, in particular, other processes can write
in between two reads performed by a process, and, as mentioned before,
different interleavings of reads and writes result in different views. Two
classical stronger variants of the collect instruction are considered in this
paper, including immediate snapshot used since (Borowsky and Gafni, 1993; Saks
and Zaharoglou, 1993), namely:

Snapshot::

the collect operation itself is atomic, that is, all registers are read
simultaneously at once, in an atomic manner.

Immediate Snapshot::

the write-snapshot sequence of operations is itself atomic, that is, not only
all registers are read simultaneously at once, but the snapshot occurs
“immediately” after the write operation, in an atomic manner.

It is easier to reason about algorithms using (immediate) snapshots than with
algorithms using sequential collect as the number of interleavings between
writes and reads are more restricted when using snapshots than when using
collects, as it should appear clear in the next subsection.

Regarding linearizability, note that while the atomic read, write, and
snapshot instructions may be supposed to occur at different times, two
immediate snapshots, say by processes $i$ and $j$, may be executed
concurrently. In this case, processes $i$ (resp., $j$) is supposed to read
$R[j]$ (resp., $R[i]$) after process $j$ (resp., $i$) has written in it.

####  A.3.4. Topological transformations

Given a simplex $\sigma=\\{(i,x_{i}):i\in I\\}\in\mathcal{I}$ for some
$I\subseteq[n]$, one round of communication performed by the processes in
$\mbox{\sc{id}}(\sigma)$ as in the generic round-based Algorithm 1 results in
various possible simplices, depending on the interleaving of the different
write and read operations. Such a simplex is of the form
$\tau=\\{(i,V_{i}):i\in I\\}$, where $V_{i}=\\{(j,x_{j}):j\in J_{i}\\}$ is the
view of process $i$ after one round. This view, or, equivalently, the set
$J_{i}\subseteq I$, depends on the communication model $\Xi$, i.e., collect,
snapshot, or immediate snapshot. These simplices induces a complex, denoted by
$\Xi_{1}(\sigma)$. Again, this complex has a specific form, which differs
according to the three models considered on this paper. To describe
$\Xi_{1}(\sigma)$ in the basic case of collect, we use the matrix
representation of an execution from (Kozlov, 2015; Benavides and Rajsbaum,
2018). Let us consider the set $\textsf{collect}(I)$ of matrices

$M=\left[\begin{array}[]{cccc}P_{0}&P_{1}&\dots&P_{r}\\\
I_{0}&I_{1}&\dots&I_{r}\end{array}\right]$

such that (1) $0\leq r\leq|I|-1$, (2) $P_{s}\subseteq I$ for all
$s=0,\dots,r$, (3) $P_{0}=I$, (4) $I_{0},\dots,I_{r}$ form a partition of $I$,
and (5) for every $s=0,\dots,r$, $\cup_{j=s}^{r}I_{j}\subseteq P_{s}$. The
semantic of such a matrix is that every process $i\in I_{s}$ for
$s\in\\{0,\dots,r\\}$ has read all input values from the processes in $P_{s}$,
and therefore its view after one round is $V_{i}=\\{(j,x_{j}):j\in P_{s}\\}$.
The simplex in $\Xi_{1}(\sigma)$ corresponding to the communication pattern
described by $M$ can therefore be written as $\tau_{M}=\\{(i,V_{i}):i\in I\\}$
where, for every $s\in\\{0,\dots,r\\}$ and every $i\in I_{s}$,
$V_{i}=\\{(j,x_{j}):j\in P_{s}\\}$. Given an input simplex
$\sigma\in\mathcal{I}$, the complex $\Xi_{1}(\sigma)$ can now be described as
follows, depending on the communication model.

Topological transformation for collect::

$\Xi_{1}(\sigma)$ is the complex whose facets are all the simplices $\tau_{M}$
such that $M\in\textsf{collect}(\mbox{\sc{id}}(\sigma))$.

Topological transformation for snapshot::

$\Xi_{1}(\sigma)$ is the complex whose facets are all the simplices $\tau_{M}$
such that $M\in\textsf{collect}(\mbox{\sc{id}}(\sigma))$ and, for every $0\leq
i<j\leq r$, $P_{i}\subseteq P_{j}$ or $P_{j}\subseteq P_{i}$.111This is
because, for any two processes $p$ and $q$, either $p$ performs its snapshot
before $q$, or after $q$. In other words, two views must be comparable
according the subset relation, and thus the views form a chain according to
the subset order relation.

Topological transformation for immediate snapshot::

$\Xi_{1}(\sigma)$ is the complex whose facets are all the simplices $\tau_{M}$
such that $M\in\textsf{collect}(\mbox{\sc{id}}(\sigma))$ and, for every $0\leq
i\leq r$, every $p\in I_{i}$, and every $q\in P_{i}$, if $q\in I_{j}$ for some
$j\in\\{0,\dots,r\\}$ then $P_{j}\subseteq P_{i}$.222This is because, as a
snapshot occur “immediately after” its corresponding write, if process $p_{1}$
has process $p_{2}$ in its snapshot, and $p_{2}$ has process $p_{3}$ in its
snapshot, then $p_{1}$ has $p_{3}$ in its snapshots too — while this is not
necessarily the case with (non immediate) snapshots.

Figure 8 in Appendix B displays an example of these three different complexes,
for a 2-dimensional simplex $\sigma$ (i.e., a system with three processes).

##### Protocol Complex.

The operator $\Xi_{1}$ can be iterated, yielding the sequence
$(\Xi_{t})_{t\geq 0}$ where, for every simplex ${\sigma\in\mathcal{I}}$,
$\Xi_{0}(\sigma)=\sigma$, and, for every $t\geq 1$,
$\Xi_{t}(\sigma)=\Xi_{1}(\Xi_{t-1}(\sigma))$. For every input complex
$\mathcal{I}$, and every $t\geq 0$, the complex $\Xi_{t}(\mathcal{I})$ is
called the _protocol complex_ after $t$ rounds. This complex is the union, for
all simplices $\sigma\in\mathcal{I}$ of the complex $\Xi_{t}(\sigma)$
resulting from $t$ rounds starting from input $\sigma$.

Note that for any two input simplices $\sigma=\\{(i,x_{i}):i\in I\\}$ and
$\sigma^{\prime}=\\{(i,x^{\prime}_{i}):i\in I\\}$, the complexes
$\Xi_{1}(\sigma)$ and $\Xi_{1}(\sigma^{\prime})$ are isomorphic. We denote by
$\chi:\Xi_{1}(\sigma)\to\Xi_{1}(\sigma^{\prime})$ the canonical isomorphism
that maps vertex $v=(i,\\{(j,x_{j}):j\in J_{i}\\})$ of $\Xi_{1}(\sigma)$ to
vertex $\chi(v)={(i,\\{(j,x^{\prime}_{j}):j\in J_{i}\\})}$ of
$\Xi_{1}(\sigma^{\prime})$.

###  A.4. Task Solvability

Let $\Xi$ be a round-based full-information model, and let
$\Pi=(\mathcal{I},\mathcal{O},\Delta)$ be a task. Recall that a task $\Pi$ is
solvable in $t$ rounds if there exists a simplicial map
$f:\Xi_{t}(\mathcal{I})\to\mathcal{O}$ from the $t$-round protocol complex to
the output complex that agrees with $\Delta$, i.e., for every
$\sigma\in\mathcal{I}$, $f(\Xi_{t}(\sigma))\subseteq\Delta(\sigma).$ Indeed,
the simplicial map $f$ is merely the function $f$ used in Algorithm 1 for
computing the output values of the processes. The former agrees with the
input-output specification $\Delta$ of the task if and only if the set of
outputs computed according to the latter is correct w.r.t. the given input.

##  Appendix B The 1-Round Protocol Complex

Figure 8. (a) All possible views after one round starting from the input
simplex $\sigma$ containing three processes (black, white, and red) with
respective inputs 1, 2, and 3. (b) All simplices in $\Xi_{1}(\sigma)$
resulting from immediate snapshot — they result from a chromatic subdivision
of $\sigma$. (c) All simplices in $\Xi_{1}(\sigma)$ resulting from snapshot
but not from immediate snapshot. (d) All simplices in $\Xi_{1}(\sigma)$
resulting from collect, but neither from snapshot nor immediate snapshot.