# A speedup theorem for asynchronous computation with applications to consensus and approximate agreement

Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum

► To cite this version:

Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum. A speedup theorem for asynchronous computation with applications to consensus and approximate agreement. Distributed Computing, 2025, 38, pp.163-183. 10.1007/s00446-025-00480-0 . hal-05114147

HAL Id: hal-05114147

https://u-paris.hal.science/hal-05114147v1

Submitted on 16 Jun 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# A speedup theorem for asynchronous computation with applications to consensus and approximate agreement

Pierre Fraigniaud<fnref n="1" /> · Ami Paz<fnref n="2" /> · Sergio Rajsbaum<fnref n="3" />

Received: 18 November 2022 / Accepted: 13 March 2025

© The Author(s) 2025

## 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 $Π$ and a given computational model $M$, we define a new task, called the *closure* of $Π$ with respect to $M$. The asynchronous speedup theorem states that if a task $Π$ is solvable in $t \ge 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.

## 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 [2, 21, 33]. 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 [18] and indistinguishability [4] 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 [25]. 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 [6, 12] 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 \ge 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 $Π = (I, O, Δ)$ is defined by a collection $I$ of possible input configurations, a collection $O$ of possible output configurations, and a map $Δ: I \to 2^O$ specifying an input-output relation. A subset of processes starting with inputs as

<figure><img src="image_2.png" /></figure>

<footnote>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.</footnote>

<footnote>Ami Paz
ami.paz@lisn.fr</footnote>

<footnote>Pierre Fraigniaud
pierre.fraigniaud@irif.fr</footnote>

<footnote>Sergio Rajsbaum
rajsbaum@im.unam.mx</footnote>

<footnote n="1">1 IRIF, CNRS and Université Paris Cité, Paris, France</footnote>

<footnote n="2">2 LISN, CNRS and Université Paris-Saclay, Gif-sur-Yvette, France</footnote>

<footnote n="3">3 Instituto de Matemáticas, UNAM, Mexico City, Mexico</footnote>
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 $CL_M(\Pi) = (\mathcal{I}, \mathcal{O}', \Delta')$, 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 \ge 1$, if a task $\Pi$ is solvable in $t$ rounds in $M$, then $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 “$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 $CL_M(\Pi)$ then depends on the nature of these objects. Intuitively, $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 $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'(\sigma)$ of legal output configurations for $\sigma$ in the closure task $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 1). Recall that in a solo execution, there is fixed process that takes its steps before the other processes in each of the rounds. Such models include the usual wait-free iterated immediate snapshot (IIS), iterated snapshot, and iterated collect models (see Sect. 2.1 for further discussion of the models and the relations between them). They also include affine models [32] that allow solo executions, such as the k-concurrency model [22]. 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 [27], 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 1): 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 2). We illustrate its usefulness with a new proof of the impossibility for consensus among $n \ge 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 [24] can help solving a problem faster. We present two examples of objects that are more powerful than read/write registers in terms of solvability, 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 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 \ge 3$ processes with rational inputs in $[0, 1]$ is at least $\lceil \log_2(1/\epsilon) \rceil$ (Corollary 3), which is tight. We then show that augmenting the model with test&set objects does not reduce the time complexity at all (Theorem 3), 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 \ge 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 4), 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 of $-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 [3], and there exists an algorithm for solving multi-value consensus in $\lceil \log_2 n \rceil$ rounds [35, 37] 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) [18] showed that consensus cannot be solved in a message passing system even if only one process may fail by halting. Later, Herlihy [24] 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 [28] 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 [39] and by Borowsky and Gafni [8], 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 [18] or connectivity analysis [28], in addition to indirect, reduction [24] or simulation techniques e.g. [14]. Our technique of computing the closure of consensus provides a novel way for proving such impossibility results. Regarding complexity issues, Hoest and Shavit [29] 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 [1] used similar techniques for proving time upper bounds, and Ellen, Gelashvili, and Zhu [17] 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 [16] 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 [3] 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 [29], 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 \ge 3$. A similar result was recently proved in the context of dynamic networks by Függer, Nowak and Schwarz [19], 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 [29] prove their lower bounds using a global analysis of the protocol complex, while Függer, Nowak and Schwarz [19] extend the notion of valency used for consensus [18, 34] 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 [24] 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. [23, 30] using simulations, or using topology e.g. [26]. 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 [6, 12] 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 [13, 20]. An extension of the speedup technique in [6, 12] to arbitrary round-based full-information models has been proposed in [7]. 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 [5], and specifically the iterated case [38]. We adopt a standard framework for modeling distributed computation, by using concepts borrowed from algebraic topology [25]. The reader unfamiliar with these notions is referred to Appendix A for more details.

## 2.1 Iterated models

We consider distributed systems with $n \ge 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. The processes start with inputs according to the task being solved, then follow a protocol which defines the sequence of operations they perform, and finally produce outputs. The outputs must satisfy the input/output relation defined by the task (see below). A protocol is wait-free if a process decides on an output after a finite number of its own operations, regardless of the behavior of other processes. A task is wait-free solvable if there is a wait-free protocol solving it.

We focus on generic round-based algorithms, with atomic read and write operations. Specifically, Algorithm 1 is for the iterated model, in which the shared-memory is organized in arrays $M_r$, $r \ge 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.

<caption>**Algorithm 1:** Code for process $i \in [n]$ with input $x_i$</caption>

1 $V_i \leftarrow x_i$
2 **for** $r = 1$ **to** $t$
3 &nbsp;&nbsp;&nbsp;&nbsp;**write** $(i, V_i)$ in register $M_r[i]$
4 &nbsp;&nbsp;&nbsp;&nbsp;$V_i \leftarrow \text{collect } M_r$[1..$n$]
5 **end**
6 $y_i \leftarrow f(i, V_i)$
7 **output** $y_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 [5]. Immediate snapshot [8, 39] 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.

In addition to the IIS model, we study extensions of this model where it is augmented with one-shot objects.<fnref n="1" /> We consider test&set and binary consensus objects; generally, these objects allow to solve tasks unsolvable in the IIS model, but we focus on their ability to facilitate wait-free solving approximate agreement faster.

## 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 = \text{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 $\text{ID}(\tau) = \text{ID}(\sigma)$ that are legal with respect to $\sigma$. That is, assuming that only the processes in $\text{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' \in \mathcal{I}$, if $\sigma' \subseteq \sigma$ then $\Delta(\sigma') \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 = \text{ID}(\sigma) \subseteq [n]$, one round of communication performed by the processes in $\text{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

<footnote n="1">¹ Here we are only interested in oracles or black box protocols that solve tasks, and use the term “objects” for them. For a thorough discussion of the differences between tasks and objects in the classical sense of sequential specifications see, e.g., [15].</footnote>
$\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$ [28]. 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 \ge 0}$ where, for every simplex $\sigma \in \mathcal{I}$, $\mathcal{P}^{(0)}(\sigma) = \sigma$, and, for every $t \ge 1$, $\mathcal{P}^{(t)}(\sigma) = \Xi(\mathcal{P}^{(t-1)}(\sigma))$. For every input complex $\mathcal{I}$, and every $t \ge 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' = \{(i, x'_i) : i \in I\}$, the complexes $\mathcal{P}^{(1)}(\sigma)$ and $\mathcal{P}^{(1)}(\sigma')$ are isomorphic. We denote by

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

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'_i) : j \in J_i\})$ of $\mathcal{P}^{(1)}(\sigma')$. 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 (Fig. 2). As it will be shown later, given a computational model $M$,

<figure><img src="image_3.png" /><figcaption>Fig. 1 Local task</figcaption></figure>

and given a task $\Pi$, the closure of $\Pi$ w.r.t. $M$, denoted by $\mathrm{CL}_M(\Pi)$, is a simpler task in the sense that if $\Pi$ is solvable in $t$ rounds in model $M$, then $\mathrm{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 (Fig. 1), which does not depend on $M$, but only on $\Pi$. Intuitively, this task closes the one-round gap between the round-complexities of $\mathrm{CL}_M(\Pi)$ and $\Pi$ by taking the outputs of $\mathrm{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'$ of $\tau$, $\mathrm{ID}(v) \neq \mathrm{ID}(v')$. Intuitively, to every simplex $\sigma \in \mathcal{I}$, and to every chromatic set of output vertices $\tau \subseteq V(\mathcal{O})$ satisfying $\mathrm{ID}(\tau) = \mathrm{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 $\mathrm{proj}_I(\mathcal{K})$ the subcomplex of $\mathcal{K}$ induced by the vertices with IDs in $I$.

**Definition 1** 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 $\mathrm{ID}(\tau) = \mathrm{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) for every vertex $v \in \tau : \Delta_{\tau,\sigma}(v) = \{v\}$;

(2) for every $\tau' \subseteq \tau$ with $|\tau'| > 1 : \Delta_{\tau,\sigma}(\tau') = \mathrm{proj}_{\mathrm{ID}(\tau')}(\Delta(\sigma))$.

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'$ of $\tau$ with dimension
greater than 0, the image of $\tau'$ by $\Delta_{\tau,\sigma}$ is any simplex of $\Delta(\sigma)$ colored with the IDs of the processes in $\tau'$.

**Remark** Given the local task $\Pi_{\tau,\sigma} = (\tau, \Delta(\sigma), \Delta_{\tau,\sigma})$ and $\tau' \subseteq \tau$, the set $\Delta_{\tau,\sigma}(\tau')$ induces a subcomplex of $\Delta(\sigma)$, potentially reduced to a single vertex whenever $|\tau'| = 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 $\text{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 2** The closure of a task $\Pi = (\mathcal{I}, \mathcal{O}, \Delta)$ with respect to a communication model $M$ is the task $\text{CL}_M(\Pi) = (\mathcal{I}, \mathcal{O}', \Delta')$ where $V(\mathcal{O}') = V(\mathcal{O})$, and, for any $\sigma \in \mathcal{I}$ and any set $\tau \subseteq V(\mathcal{O})$, we let $\tau \in \Delta'(\sigma)$ if $\tau$ is chromatic, $\text{ID}(\tau) = \text{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}'$ are the images of $\Delta'$, and all their faces.

Figure 2 illustrates Definition 2, and in particular of how the map $\Delta'$ 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'(\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'$.

**Remark** Given a task $\Pi = (\mathcal{I}, \mathcal{O}, \Delta)$ and its closure $\text{CL}_M(\Pi) = (\mathcal{I}, \mathcal{O}', \Delta')$ w.r.t. some model $M$, we have $\Delta(\sigma) \subseteq \Delta'(\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 $\text{ID}(\tau) = \text{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'(\sigma)$ for every $\sigma \in \mathcal{I}$, the closure $\text{CL}_M(\Pi) = (\mathcal{I}, \mathcal{O}', \Delta')$ 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 1** Let $M$ be an iterated model allowing solo executions. For every $t \ge 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 \ge 1$, and assume that $\Pi$ is solvable in $t$ rounds in model $M$. Let $\text{CL}_M(\Pi) = (\mathcal{I}, \mathcal{O}', \Delta')$ be the closure of $\Pi$ w.r.t. $M$. Our goal is to show that $\text{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': \mathcal{P}^{(t-1)} \to \mathcal{O}'$, that agrees with $\Delta'$. 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 Fig. 3). We merely define $f'(i, V_i) = f(i, \{(i, V_i)\})$. That is, $f'(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'(i, V_i)$ is a vertex of $\mathcal{O}'$, as $V(\mathcal{O}') = V(\mathcal{O})$.

Let us show that $f'$ is simplicial and agrees with $\Delta'$. 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 Fig. 3). We aim at establishing that $f'(\rho)$ is a simplex of $\Delta'(\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'(\rho)$. For every $i \in I$, let $(i, y_i) = f'(i, V_i)$ be the output vertex returned by $f'$ for process $i$ with view $V_i$ in $\mathcal{P}^{(t-1)}(\sigma)$. We have $\tau = f'(\rho) = \{f'(i, V_i) : i \in I\} = \{(i, y_i) : i \in I\}$. To establish that $f'$ is simplicial and agrees with $\Delta'$, it is sufficient to show that $\tau$ is a simplex of $\Delta'(\sigma)$.

To show that $\tau \in \Delta'(\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 \text{ID}(\tau)$, process $i$ starts
<figure><img src="image_4.png" /><figcaption>**Fig. 3** Construction in the proof of Theorem 1</figcaption></figure>

<figure><img src="image_5.png" /></figure>

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 Fig. 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. Equation (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 \mathrm{ID}(\tau)$. We have

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' \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')) \subseteq \Delta_{\tau,\sigma}(\tau')$, consider a simplex $\kappa' \in \mathcal{P}^{(1)}(\tau')$ with $\mathrm{ID}(\kappa') = \mathrm{ID}(\tau')$, and let $\rho' = \chi(\kappa')$ be the corresponding simplex in $\mathcal{P}^{(1)}(\rho)$. By the definition of the map $g$, we have $g(\kappa') = f \circ \chi(\kappa') = f(\rho')$. Since $f$ solves the task $\Pi$ with input $\sigma \in \mathcal{I}$, we have $f(\rho') \in \Delta(\sigma)$. Since $\mathrm{ID}(f(\rho')) = \mathrm{ID}(\rho')$, we get that $f(\rho') \in \mathrm{proj}_{\mathrm{ID}(\tau')}(\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'(\sigma)$. As a consequence, $f'$ is simplicial and agrees with $\Delta'$, which completes the proof. □

$$g(i, \{(i, y_i)\}) = f(i, \{(i, V_i)\}) = f'(i, V_i) = (i, y_i).$$
## 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 $Π = (\mathcal{I}, \mathcal{O}, \Delta)$ is said to be a fixed-point for model $M$ whenever $\mathrm{CL}_M(Π) = Π$.

**Lemma 1** A task $Π$ 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 \ge 1$ such that $Π$ is solvable in $t$ rounds in $M$. By the speedup theorem, $\mathrm{CL}_M(Π) = Π$ 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 $Π$ is solvable in zero rounds in $M$. □

Recall that the binary consensus task for $n$ processes is the task $(\mathcal{I}, \mathcal{O}, \Delta)$ defined as 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) = \begin{cases} \{\mathrm{proj}_I(\tau_0), \mathrm{proj}_I(\tau_1)\} & \exists i, j \in I \text{ s.t. } x_i \neq x_j \\ \{\sigma\} & \text{otherwise.} \end{cases} $$

The impossibility of solving binary consensus is a classical result [18], and its proof usually goes by showing that it is impossible to solve consensus in zero rounds, and then constructing an execution in which processes cannot decide by adding one round at a time. We take a “backward” approach, showing that solvability in $r$ rounds implies solvability in $r-1$ rounds, all the way down to zero rounds. While this is not very different from the original proof, it allows us to demonstrate the use of Lemma 1 before moving on to more intricate cases.

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

*Proof* Let $Π$ 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 $\mathrm{CL}_M(Π) = Π$. After proving this, the impossibility of consensus is immediate from Lemma 1, 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'(\sigma) = \Delta(\sigma)$ for every $\sigma = \{(i, x_i) : i \in I\} \in \mathcal{I}$. Since, as noticed before, $\Delta(\sigma) \subseteq \Delta'(\sigma)$ for every task, it suffices to show $\Delta'(\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'(\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'(\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'(\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

$$ \begin{aligned} & (i, \{(i, y_i)\}) \quad (j, \{(i, y_i), (j, y_j)\}) \\ & (i, \{(i, y_i), (j, y_j)\}) \quad (j, \{(j, y_j)\}) \end{aligned} $$

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)\}) = \mathrm{proj}_{\{i,j\}}(\Delta(\sigma))$. We have $\mathrm{proj}_{\{i,j\}}(\Delta(\sigma)) = \{\mathrm{proj}_{\{i,j\}}(\tau_0), \mathrm{proj}_{\{i,j\}}(\tau_1)\}$. It follows that either all edges $f(e_1), f(e_2)$, and $f(e_3)$ are equal to $\mathrm{proj}_{\{i,j\}}(\tau_0)$, or all of them are equal to $\mathrm{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

We consider generic round-based algorithms in a model augmented with a black box object **B** as displayed in Algorithm 2. This algorithm is similar to Algorithm 1 except that a call to a black box **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 **B**, where $\mathbf{B}_t$ 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 **B** at a given round $r$, each
<table><caption>**Algorithm 2:** Code for process $i \in [n]$ with input $x_i$</caption><thead><tr><th>1</th><th>V<sub>i</sub> &larr; x<sub>i</sub></th></tr></thead><tbody><tr><td>2</td><td>for r &larr; 1 to t</td></tr><tr><td>3</td><td>&nbsp;&nbsp;&nbsp;&nbsp;write (i, V<sub>i</sub>) to M<sub>r</sub>[i]</td></tr><tr><td>4</td><td>&nbsp;&nbsp;&nbsp;&nbsp;a<sub>i</sub> &larr; &alpha;(i, V<sub>i</sub>, r)</td></tr><tr><td>5</td><td>&nbsp;&nbsp;&nbsp;&nbsp;b<sub>i</sub> &larr; B<sub>r</sub>(a<sub>i</sub>)</td></tr><tr><td>6</td><td>&nbsp;&nbsp;&nbsp;&nbsp;C<sub>i</sub> &larr; collect M<sub>r</sub>[1..n]</td></tr><tr><td>7</td><td>&nbsp;&nbsp;&nbsp;&nbsp;V<sub>i</sub> &larr; (b<sub>i</sub>, C<sub>i</sub>)</td></tr><tr><td>8</td><td>end</td></tr><tr><td>9</td><td>y<sub>i</sub> &larr; f(i, V<sub>i</sub>)</td></tr><tr><td>10</td><td>output y<sub>i</sub>.</td></tr></tbody></table>

process $i \in [n]$ computes an input value $a_i$ for $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 $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 $B_r$, and the collection of the views of the other processes.

**Remark** In this paper, we assume that the black box object **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, **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 2** Let $M$ be an iterated model augmented with a black box allowing solo executions. For every $t \ge 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 1, 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': \mathcal{P}^{(t-1)} \to \mathcal{O}'$, that agrees with $\Delta'$. Let $(i, V_i) \in \mathcal{P}^{(t-1)}$ be a vertex of $\mathcal{P}^{(t-1)}$. We define $f'(i, V_i) = f(i, (b_i, \{(i, V_i)\}))$, where $b_i = B_r(a_i)$ is the output of the black box $B$ invoked at round $t$ with $a_i = \alpha(i, V_i, t)$ as input, whenever process $i$ is running solo in $B$. Let us show that $f'$ is simplicial and agrees with $\Delta'$. 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'(\rho) = \{(i, y_i) : i \in I\}$. To show that $\tau \in \Delta'(\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 1, 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 = B_1(a_i) = B_r(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(i, (b_i, z_i)) = f(i, (b_i, W_i))$ 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 1, 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 [24], 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 Fig. 4 is simplicial, and its composition with the map $\Xi: \mathcal{I} \to \mathcal{P}^{(1)}$ agrees with the specification of consensus.

In contrast, we show that for more than two processes, binary consensus is not solvable even using test&set, by applying Theorem 2. Figure 5 describes the protocol complex
<figure><img src="image_6.png" /><figcaption>**Fig. 5** 1-round protocol complex for three processes using test&set</figcaption></figure>

$\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, Fig. 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.

**Corollary 2** 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 1, as the binary consensus task $\Pi_{\text{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{CON}}$, even if only two processes $i$ and $j$ participate, they must agree on the same value, while in the closure task $\text{CL}_M(\Pi_{\text{CON}}) = (\mathcal{I}, \mathcal{O}', \Delta')$ 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'(\sigma) = \{( (i, y_i), (j, y_j) ) : (y_i, y_j) \in \{0, 1\}^2 \}$.

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 $\text{CL}_M(\Pi) = (\mathcal{I}, \mathcal{O}', \Delta')$ be the closure task of $\Pi$. Let us fix simplices $\sigma = \{(i, x_i) | i \in I\} \in \mathcal{I}$ and $\tau = \{(i, y_i), | i \in I\} \in \Delta'(\sigma)$ for a non-empty set $I \subseteq [n]$. If $|I| \le 2$, then any subset of $\tau' \subseteq V(\Delta(\sigma))$ is already a simplex of $\Delta(\sigma)$, and we are done. Let us now consider the case of $|I| \ge 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(\ell, (t_\ell, \{(\ell, y_\ell)\})) = (\ell, y_\ell)$, where $t_\ell$ is the output of test&set, which is actually equal to 1 since the vertex $(\ell, (t_\ell, \{(\ell, y_\ell)\}))$ represents a solo step by process $\ell$.

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

$$ \rho_{i,j,k} = \left\{ (i, (1, \{(i, y_i)\})), (j, (0, \{(i, y_i), (j, y_j)\})), (k, (0, \{(i, y_i), (j, y_j), (k, y_k)\})) \right\}. $$

and

$$ \rho_{j,i,k} = \left\{ (j, (1, \{(j, y_j)\})), (i, (0, \{(i, y_i), (j, y_j)\})), (k, (0, \{(i, y_i), (j, y_j), (k, y_k)\})) \right\}. $$
<figure><img src="image_7.png" /><figcaption>**Fig. 6** Consensus is not solvable among $n > 2$ processes, even using test&set</figcaption></figure>

Let $\gamma = f(k, (0, \{(i, y_i), (j, y_j), (k, y_k)\}))$ be the output of $f$ on the vertex $(k, (0, \{(i, y_i), (j, y_j), (k, y_k)\}))$ of $\mathcal{P}^{(1)}(\sigma)$. Since $f$ agrees with $\Delta_{\tau,\sigma}$, we have that $f(\rho_{i,j,k}) \subseteq \text{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) | \ell \in I\}$, which implies that $\tau \in \Delta(\sigma)$, as claimed.

The rest of the proof is similar to the proof of Lemma 1, but using Theorem 2. That is, if $\Pi$ was solvable in $t$ rounds in $M$ among $n \ge 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 \ge 3$ processes, consensus is not solvable. $\square$

## 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 \ge 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 3** Given a parameter $\epsilon \in (0, 1]$ which is an integral multiple of $1/m$ for some integer $m \ge 1$, the $\epsilon$-approximate agreement for $n$ processes is the task $(\mathcal{I}, \mathcal{O}, \Delta)$,

where

$$ \mathcal{I} = \{ \{(i, x_i) : i \in I\} | (\emptyset \neq I \subseteq [n]) \\ \wedge (\forall i \in I, x_i \in \{0, 1/m, 2/m, \dots, 1\}) \} $$

$$ \mathcal{O} = \{ \{(i, y_i) : i \in I\} | (\emptyset \neq I \subseteq [n]), \\ (\forall i \in I, y_i \in \{0, 1/m, 2/m, \dots, 1\}) \\ \wedge (\forall i, j \in I, |y_i - y_j| \le \epsilon) \} $$

$$ \begin{aligned} \Delta : \mathcal{I} &\to 2^{\mathcal{O}} & \text{where } \Delta(\{(i, x_i) : i \in I\}) \\ &= \{\{(i, y_i) : i \in I\} \in \mathcal{O} | \\ &\quad \forall j \in I, \min\{x_i : i \in I\} \le y_j \le \max\{x_i : i \in I\}\} \end{aligned} $$

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 4** 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 [29]. 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 \ge 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 \ge 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 \ge 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 $\mathrm{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 $\mathrm{CL}_M(\Pi_\epsilon) = (\mathcal{I}, \mathcal{O}'_\epsilon, \Delta'_\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'_\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'_\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'_\epsilon(\sigma)$. We conclude that for vertices, $\Delta'_\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(\sigma)$, and show $\tau \in \Delta_{3\epsilon}(\sigma)$. To this end, we show $(1) \min\{x_1, x_2\} \le y_i \le \max\{x_1, x_2\}$ for all $i \in \{1, 2\}$, and $(2) |y_1 - y_2| \le 3\epsilon$.

Since $\tau \in \Delta'_\epsilon(\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\} \le y_i \le \max\{x_1, x_2\}$, and thus property (1) holds. Let us denote by $\gamma_1, \gamma_2$ the two values satisfying

$$ 
\begin{align*} 
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{align*} 
$$

Since $f$ solves the local task $\Pi_{\tau,\sigma} = (\tau, \Delta_\epsilon(\sigma), \Delta_{\tau,\sigma})$, we have $|y_2 - y_1| \le |y_2 - \gamma_1| + |\gamma_1 - \gamma_2| + |\gamma_2 - y_1| \le 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 \le 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

$$ 
\begin{align} 
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{align} 
$$

The map $f$ solves $\epsilon$-approximate agreement whenever $y_2 - y_1 \le 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'_\epsilon(\sigma)$. We conclude that, for edges as well, $\Delta'_\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 \ge 3$ processes, then the closure $\mathrm{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 \ge 3$ processes, and let $\mathrm{CL}_M(\Pi_\epsilon) = (\mathcal{I}, \mathcal{O}'_\epsilon, \Delta'_\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'_\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| \ge 2$.

Fix an input simplex $\sigma = \{(i, x_i) | 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'_\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'_\epsilon(\sigma) = \{(j, y_j) | j \in I, \min\{x_i : i \in I\} \le y_j \le \max\{x_i : i \in I\} = \Delta_{2\epsilon}(\sigma)$. For the case $|I| \ge 3$, we prove containment in both directions. First, we consider a simplex $\tau = \{(i, y_i) | i \in I\} \in \Delta'_\epsilon(\sigma)$, and show $\tau \in \Delta_{2\epsilon}(\sigma)$, i.e., (1) $\min\{x_i : i \in I\} \le y_i' \le \max\{x_i : i \in I\}$ for all $i' \in I$, and (2) $|y_i - y_i'| \le 2\epsilon$ for all $i, i' \in I$.

Since $\tau \in \Delta'_\epsilon(\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{aligned}
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{aligned}
$$

Since $f$ solves the local task $\Pi_{\tau,\sigma} = (\tau, \Delta_\epsilon(\sigma), \Delta_{\tau,\sigma})$, we have $|y_i - y_j| \le |y_j - \gamma| + |\gamma - y_i| \le 2\epsilon$. It follows that $\tau \in \Delta_{2\epsilon}(\sigma)$.

Conversely, let us consider $\tau = \{(i, y_i) | 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$,

$$ f(i, \{y_j : j \in J\}) = (i, \min\{\max\{y_j : j \in J\}, \min\{y_j : j \in J\} + \epsilon\}) \quad (3) $$

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'$, and let $J, J'$ be the sets of processes that these two processes see in their immediate snapshot, respectively. Assume, w.l.o.g., that $J' \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 | j \in J\}$, and let $y'_{\min}$ and $y'_{\max}$ be the minimal and maximal values in $\{y'_{j} | j \in J'\}$. Note that $y_{\min} \le y'_{\min} \le y'_{\max} \le y_{\max} \le y_{\min} + 2\epsilon$. If $y'_{\max} \le y_{\min} + \epsilon$ then the facts that $f(i, \{y_j : j \in J\}) \le y_{\min} + \epsilon$ and $f(i, \{y_j : j \in J'\}) \le y'_{\max}$ imply that both processes output values in $[y_{\min}, y_{\min} + \epsilon]$, and we are done. Otherwise, $y_{\min} + \epsilon < y'_{\max} \le y_{\max}$, and so process $i$ outputs $y_{\min} + \epsilon$, while process $i'$ outputs a value in $[y_{\min}, y_{\min} + 2\epsilon]$, and we are done too.

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

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

**Corollary 3** 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 1 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 \ge 1$, which immediately implies the lower bound.

If $n \ge 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 \ge 1$, and the lower bound follows. $\square$

**Remark** The bounds in Corollary 3 are known to be tight [29]. In fact, the tightness of our lower bounds is also directly implied by our proofs, as specified by Eqs. 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 2), we show that it still takes at least $\lceil \log_2 1/\epsilon \rceil$ rounds to solve $\epsilon$-approximate agreement.

**Theorem 3** The number of rounds required for solving the $\epsilon$-approximate agreement task in the wait-free IIS model augmented with test&set among $n \ge 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 \ge 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 \ge 3$ processes, and let $\text{CL}_M(\Pi_{\epsilon}) = (\mathcal{I}, \mathcal{O}'_{\epsilon}, \Delta'_{\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'_{\epsilon}(\sigma) = \Delta_{2\epsilon}(\sigma)$. If $|\sigma| \le 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| \ge 3$.

Consider an input simplex $\sigma = \{(i, x_i) | i \in I\} \in \mathcal{I}$, for some set $I \subseteq [n]$, $|I| \ge 3$. We consider a simplex $\tau = \{(i, y_i) | i \in I\} \in \Delta'_{\epsilon}(\sigma)$, and show $\tau \in \Delta_{2\epsilon}(\sigma)$, i.e., (1) $\min\{x_i : i \in I\} \le y_i \le \max\{x_i : i \in I\}$ for all $i \in I$, and (2) $|y_i - y_j| \le 2\epsilon$ for all $i, j \in I$.

Since $\tau \in \Delta'_{\epsilon}(\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 Fig. 6):

$$ \rho_{i,j,k} = \left\{ \begin{array}{l} (i, (1, \{(i, y_i)\})), (j, (0, \{(i, y_i), (j, y_j)\})), \\ \qquad (k, (0, \{(i, y_i), (j, y_j), (k, y_k)\})) \end{array} \right\}, $$

$$ \rho_{j,i,k} = \left\{ \begin{array}{l} (j, (1, \{(j, y_j)\})), (i, (0, \{(i, y_i), (j, y_j)\})), \\ \qquad (k, (0, \{(i, y_i), (j, y_j), (k, y_k)\})) \end{array} \right\}. $$

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

Conversely, let us consider $\tau = \{(i, y_i) | 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(i, (t_i, \{(j, y_j) | j \in J\})) = (i, \min\{\max\{y_j : j \in J\}, \min\{y_j : j \in J\} + \epsilon\}). $$

As for the proof of Claim 3, this map $f$ solves $\epsilon$-approximate agreement whenever $|y_i - y_j| \le 2\epsilon$ for every $i, j \in I$, and

<figure><img src="image_8.png" /><figcaption>**Fig. 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</figcaption></figure>

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'_{\epsilon}(\sigma)$.

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

We complete the proof of Theorem 3 by the same reasoning as in the proof of Corollary 3, but using Theorem 2 and Claim 4. Let us fix $\epsilon > 0$ and $n \ge 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 2 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 \ge 1$, which immediately implies the lower bound. $\square$

## 5.3 Approximate agreement in the wait-free IIS model with binary consensus

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 exe-
cution, 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 ⌈log₂ n⌋ rounds, by agreeing on the ID of one
of the participating processes, and then deciding on its input.
The other techniques takes ⌈log₂ 1/ε⌋ 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 4** *The number of rounds required by $n \ge 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 \ge 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 \ge 1$ may depend only on $i$ and $r$. Under these assumptions, we can strengthen the statement of Theorem 2 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 $\text{CL}_M(\Pi|\beta)$, as the task $\Pi = (\mathcal{I}, \mathcal{O}', \Delta')$ where, for every simplex $\sigma \in \mathcal{I}$, and for every chromatic set $\tau \subseteq V(\Delta(\sigma))$, we set $\tau \in \Delta'(\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 2 for the closure task with respect to functions $\beta$.

**Claim 5** For every $t \ge 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 $\text{CL}_M(\Pi|\beta)$ is solvable in $t-1$ rounds in $M$.

**Proof of claim** The proof is identical to the proof of Theo-
rem 2, 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]$. $\square$

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
$\text{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| \ge n/2$. Intuitively, when only
the processes in $S$ participate, they take no benefit of the con-
sensus 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' \subseteq S$ that may
result from another function, $\beta'$, of size at least $n/4$, such that,
whenever only the processes in $S'$ participate, the closure
with respect to $\beta'$ 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 agree-
ment 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 iter-
ations 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| \ge 5$ processes, and let $\beta : S \to \{0, 1\}$ be any function. Then there is a subset $S' \subseteq S$ of processes, with $|S'| \ge |S|/2$, such that $\text{CL}_M(\Pi|\beta)$ is the liberal version of $(2\epsilon)$-approximate agreement task whenever only the processes of $S'$ participate.

**Proof of claim** Let $S' \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' = \beta^{-1}(0)$. Note that $|S'| \ge 3$, as $|S| \ge 5$. Let $\Pi_\epsilon = (\mathcal{I}, \mathcal{O}_\epsilon, \Delta_\epsilon)$ be the liberal version of $\epsilon$-approximate agreement task on $S$, and let $\text{CL}_M(\Pi_\epsilon|\beta) = (\mathcal{I}, \mathcal{O}'_\epsilon, \Delta'_\epsilon)$. Let us denote the liberal version of $(2\epsilon)$-approximate agreement on $S$ by $\Pi_{2\epsilon} =$
(I, O₂ε, Δ₂ε). We want to show that, restricted to the processes in S', the two tasks Π₂ε and CLM(Π_ε|β) are identical. Formally, we want to show that, for every σ ∈ I with ID(σ) ⊆ S', Δ'_ε(σ) = Δ₂ε(σ). If σ = {v} is a single vertex, then Δ₂ε({v}) = {v}, and Δ'_ε({v}) = {v}, and thus Δ'_ε(σ) = Δ₂ε(σ) as desired. If |σ| = 2 then the fact that the liberal version of the tasks does not depend on ε makes the maps equal: Δ'_ε(σ) = {(j, yj) | j ∈ I, min{xᵢ: i ∈ I} ≤ yj ≤ max{xᵢ: i ∈ I}} = Δ₂ε(σ). Let us now consider an input simplex σ = {(i, xᵢ) | i ∈ I} ∈ I, for some set I ⊆ S', with |I| ≥ 3.

First, we show that Δ'_ε(σ) ⊆ Δ₂ε(σ). Let τ = {(i, yᵢ) | i ∈ I} ∈ Δ'_ε(σ). We want to show that τ ∈ Δ₂ε(σ), i.e., (1) min{xᵢ: i ∈ I} ≤ yᵢ ≤ max{xᵢ: i ∈ I} for all i ∈ I, and (2) |yᵢ - yⱼ| ≤ 2ε for all i, j ∈ I.

Since τ ∈ Δ'_ε(σ), the local task Π_{τ,σ} = (τ, Δ_ε(σ), Δ_{τ,σ}) is solvable in one round, using an algorithm in which each process i ∈ I calls the binary consensus object with input β(i) = 0. Let f : P⁽¹⁾(τ) → Δ_ε(σ) be a simplicial map solving the local task Π_{τ,σ} where f : P⁽¹⁾(τ) is the 1-round protocol complex in model M starting from τ with input 0 to the binary consensus object. Since τ ⊆ V(Δ_ε(σ)), property (1) holds.

To check property (2), note that since all processes in I ⊆ S' 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 ∈ I, and let us define γ by f(k, (0, {(i, yᵢ), (j, yⱼ), (k, yₖ)})) = (k, γ), where the 0 in this definition is the output of binary consensus at process k. Since f solves the local task Π_{τ,σ}, we have f(i, (0, {(i, yᵢ)})) = (i, yᵢ) and f(j, (0, {(j, yⱼ)})) = (j, yⱼ), 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 Π_{τ,σ} = (τ, Δ_ε(σ), Δ_{τ,σ}), we have

$$ \{ f(i, (0, \{(i, y_i)\})), f(k, (0, \{(i, y_i), (j, y_j), (k, y_k)\})) \} \in \Delta_{\epsilon}(\sigma) $$

and

$$ \{ f(j, (0, \{(j, y_j)\})), f(k, (0, \{(i, y_i), (j, y_j), (k, y_k)\})) \} \in \Delta_{\epsilon}(\sigma). $$

It follows that |yᵢ - yⱼ| ≤ |yⱼ - γ| + |γ - yᵢ| ≤ 2ε, and therefore τ ∈ Δ₂ε(σ).

Conversely, we show that Δ₂ε(σ) ⊆ Δ'_ε(σ). Let τ = {(i, yᵢ) | i ∈ I} ∈ Δ₂ε(σ). We show that the local task Π_{τ,σ} = (τ, Δ_ε(σ), Δ_{τ,σ}) is solvable in one round, using an algorithm in which each process i ∈ I calls the binary

consensus object with input β(i) = 0. Since I ⊆ S', the output of the object is necessarily 0 at every process i ∈ I. Let f : P⁽¹⁾(τ) → Δ_ε(σ) be as follows. For every i ∈ I, and every set J ⊆ I satisfying i ∈ J, we set

$$ \begin{aligned} & f(i, (0, \{y_j: j \in J\})) \\ & = (i, \min\{\max\{y_j: j \in J\}, \min\{y_j: j \in J\} + \epsilon\}). \end{aligned} $$

This map f solves ε-approximate agreement whenever |yᵢ - yⱼ| ≤ 2ε for any i, j ∈ I, and therefore it solves the local task Π_{τ,σ} = (τ, Δ_ε(σ), Δ_{τ,σ}) in one round. It follows that τ ∈ Δ'_ε(σ). This completes the proof of Claim 6. □

We now have all the ingredients for establishing the lower bound. For this purpose, let t = min{[log₂n] - 1, ⌊log₂ 1/ε⌋}, and let us assume, for the purpose of contradiction, that there exists an algorithm solving the liberal version of ε-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ε)-approximate agreement among a set S₁ ⊆ [n] of processes, with |S₁| ≥ n/2. By iterating the application of Claims 5 and 6, we eventually get a 0-round algorithm solving the liberal version of (2t⁻¹ε)-approximate agreement among a set Sₜ₋₁ ⊆ [n] of processes, with |Sₜ₋₁| ≥ n/2t⁻¹. Since t ≤ ⌊log₂n⌋ - 1, using the fact that ⌊log₂n⌋ < log₂n + 1, we get |Sₜ₋₁| > n/n log₂ n, and thus |Sₜ₋₁| ≥ 3. Also, since t ≤ ⌊log₂ 1/ε⌋, using similarly the fact that, ⌊log₂ 1/ε⌋ < log₂ 1/ε + 1, we get that 2t⁻¹ε < 1. Therefore, we get a 0-round algorithm solving the liberal version of ε'-approximate agreement among a set of at least three processes, where ε' < 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 ε-approximate agreement requires at least t rounds to be solved, and so does the (standard version of) ε-approximate agreement. □

# 6 Conclusion

Our results open many interesting questions. Our asynchronous speedup theorem is inspired by an analogous speedup technique [6, 12] 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 for iterated models and it would be highly valuable to extend it to non-iterated models. While there is no clear reason such an extension should not exist, formulating it properly will
require new definitions: even the basic complexity unit of a round used in our work does not exist when considering non-iterated models. This extension seems particularly intriguing since, while the iterated and non-iterated models are known to be equivalent with respect to task solvability [9, 10, 23, 30] (even when enriched with more powerful objects), their equivalence in terms of time complexity remains unknown.

On a different frontier, our speedup theorem assumes models allowing processes to run solo, as in standard wait-free models. It would be interesting to study extensions to affine models not possessing this property [32], 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 \ge 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.

# 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' \subseteq \sigma$, $\sigma' \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 \ge 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}'$ is a map $f : V(\mathcal{K}) \to V(\mathcal{K}')$ preserving simplices, that is, for every simplex $\sigma$, the set $f(\sigma)$ is a simplex of $\mathcal{K}'$. 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}')$. So, given a chromatic simplicial map from a chromatic complex $\mathcal{K}$ to a chromatic complex $\mathcal{K}'$, 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}'$ even if $f$ is actually defined on vertices.

A carrier map from a chromatic complex $\mathcal{K}$ to a chromatic complex $\mathcal{K}'$ is a map $\Delta : \mathcal{K} \to 2^{\mathcal{K}'}$ which maps every simplex $\sigma \in \mathcal{K}$ to a pure sub-complex of $\mathcal{K}'$ with same dimension and same colors as $\sigma$ such that, for every $\sigma' \subseteq \sigma$, $\Delta(\sigma') \subseteq \Delta(\sigma)$, i.e., $\Delta(\sigma')$ 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 $\mathrm{ID}(\sigma)$ the set of colors in $\sigma$, i.e., $\mathrm{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 $\mathrm{proj}_J(\sigma)$ the simplex $\{(i, x_i) : i \in J\}$, i.e., $\mathrm{ID}(\mathrm{proj}_J(\sigma)) = J$. That is, $\mathrm{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 \ge 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 $\mathrm{ID}(\tau) = \mathrm{ID}(\sigma)$ that are legal with respect to $\sigma$. That is, assuming that only the processes in $\mathrm{ID}(\sigma)$ participate to the computation (the set of participating processes is not known a priori to the processes in $\sigma$), there processes are allowed 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 [5], focusing on iterated models [36], following the topology approach to distributed computing [25].

### A.3.1 Read-write shared memory

A *process* is a deterministic (infinite) state machine. We consider a collection of $n \ge 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* ∈ [*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* ∈ [*n*], $R[i]$ can be *read* by any process *j* ∈ [*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* [25].

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 \ge 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 \ge 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 \ne 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 [8, 39], 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 $\mathrm{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 induce 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 [11, 31]. Let us consider the set collect($I$) of matrices

$$M = \begin{bmatrix} P_0 & P_1 & \dots & P_r \\ I_0 & I_1 & \dots & I_r \end{bmatrix}$$

such that (1) $0 \le r \le |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 \mathrm{collect}(\mathrm{ID}(\sigma))$.

**Topological transformation for snapshot:** $\Xi_1(\sigma)$ is the complex whose facets are all the simplices $\tau_M$ such that $M \in \mathrm{collect}(\mathrm{ID}(\sigma))$ and, for every $0 \le i < j \le r$, $P_i \subseteq P_j$ or $P_j \subseteq P_i$.<fnref n="2" />

**Topological transformation for immediate snapshot:** $\Xi_1(\sigma)$ is the complex whose facets are all the simplices $\tau_M$ such that $M \in \mathrm{collect}(\mathrm{ID}(\sigma))$ and, for every $0 \le i \le 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$.<fnref n="3" />

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 \ge 0}$ where, for every simplex $\sigma \in \mathcal{I}$, $\Xi_0(\sigma) = \sigma$, and, for every $t \ge 1$, $\Xi_t(\sigma) = \Xi_1(\Xi_{t-1}(\sigma))$. For every input complex $\mathcal{I}$, and every $t \ge 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' = \{(i, x'_i) : i \in I\}$, the complexes $\Xi_1(\sigma)$ and $\Xi_1(\sigma')$ are isomorphic. We denote by $\chi : \Xi_1(\sigma) \to \Xi_1(\sigma')$ 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'_j) : j \in J_i\})$ of $\Xi_1(\sigma')$.

### 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.

## B The 1-round protocol complex

<footnote n="2">² This 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.</footnote>

<footnote n="3">³ This 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.</footnote>
**Fig. 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

## B THE 1-ROUND PROTOCOL COMPLEX

<figure><img src="image_9.png" /></figure>

**Funding** Open access funding provided by Université Paris-Saclay.

**Data availability** There is no raw data that relates to this research.

## Declarations

**Conflict of interest** The authors have no Conflict of interest to disclose.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

## References

1. Attiya, H., Castañeda, A., Herlihy, M., Paz, A.: Bounds on the step and namespace complexity of renaming. SIAM J. Comput. 48(1), 1–32 (2019)

2. Attiya, H., Ellen, F.: Impossibility Results for Distributed Computing. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers (2014)

3. Aspnes, J., Herlihy, M.: Wait-free data structures in the asynchronous PRAM model. In: 2nd ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 340–349 (1990)

4. Attiya, H., Rajsbaum, S.: Indistinguishability. Commun. ACM 63(5), 90–99 (2020)

5. Attiya, H., Welch, J.: Distributed Computing: Fundamentals. Simulations and Advanced Topics. John Wiley & Sons, Hoboken (2004)

6. Balliu, A., Brandt, S., Hirvonen, J., Olivetti, D., Rabie, M., Suomela, J.: Lower bounds for maximal matchings and maximal independent sets. In: 60th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 481–497 (2019)

7. Bastide, P., Fraigniaud, P.: Brief annoucement: On extending Brandt's speedup theorem from LOCAL to round-based full-information models. In: 35th International Symposium on Distributed Computing (DISC), volume 209 of LIPIcs, pp. 47:1–47:4. Schloss Dagstuhl (2021)

8. Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: 25 ACM Symposium on Theory of Computing (STOC), pp. 91–100 (1993)

9. Borowsky, E., Gafni, E.: A simple algorithmically reasoned characterization of wait-free computations (extended abstract). In: 16th ACM Symposium on Principles of Distributed Computing (PODC), pp. 189–198 (1997)

10. Bouzid, Z., Gafni, E., Kuznetsov, P.: Strong equivalence relations for iterated models. In: 18th International Conference on Principles of Distributed Systems (OPODIS), LNCS 8878, pp. 139–154. Springer (2014)
11. Benavides, F., Rajsbaum, S.: Collapsibility of read/write models using discrete morse theory. J. Appl. Comput. Topol. **1**(3-4), 365-396 (2018)

12. Brandt, S.: An automatic speedup theorem for distributed problems. In: 38th ACM Symposium on Principles of Distributed Computing (PODC), pp. 379-388 (2019)

13. Castañeda, A., Fraigniaud, P., Paz, A., Rajsbaum, S., Roy, M., Travers, C.: A topological perspective on distributed network algorithms. Theor. Comput. Sci. **849**, 121-137 (2021)

14. Chandra, T., Hadzilacos, V., Jayanti, P., Toueg, S.: Generalized irreducibility of consensus and the equivalence of t-resilient and wait-free implementations of consensus. SIAM J. Comput. **34**(2), 333-357 (2005)

15. Castañeda, A., Rajsbaum, S., Raynal, M.: Unifying concurrent objects and distributed tasks: interval-linearizability. J. ACM **65**(6), 45:1-45:42 (2018)

16. Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. J. ACM **33**(3), 499-516 (1986)

17. Ellen, F., Gelashvili, R., Zhu, L.: Revisionist simulations: A new approach to proving space lower bounds. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC, pp. 61-70. ACM (2018)

18. Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM **32**(2), 374-382 (1985)

19. Függer, M., Nowak, T., Schwarz, M.: Tight bounds for asymptotic and approximate consensus. J. ACM **68**(6), 1 (2021)

20. Fraigniaud, P., Paz, A.: The topology of local computing in networks. In: 47th International Colloquium on Automata, Languages, and Programming (ICALP), vol.168 of LIPIcs, pp. 128:1-128:18. Schloss Dagstuhl (2020)

21. Fich, F.E., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distrib. Comput. **16**(2-3), 121-163 (2003)

22. Gafni, E., Guerraoui, R.: Generalized universality. In: Proceedings of the 22nd International Conference on Concurrency Theory, CONCUR'11, pp. 17-27. Springer-Verlag, Berlin, Heidelberg (2011)

23. Gafni, E., Rajsbaum, S.: Distributed programming with tasks. In: 14th International Conference on Principles of Distributed Systems (OPODIS), LNCS 6490, pp. 205-218. Springer (2010)

24. Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. **13**(1), 124-149 (1991)

25. Herlihy, M., Kozlov, D.N., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann (2013)

26. Herlihy, M., Rajsbaum, S.: Algebraic topology and distributed computing: a primer. In: Computer Science Today: Recent Trends and Developments, volume 1000 of LNCS, pp. 203-217. Springer (1995)

27. Herlihy, M., Rajsbaum, S., Raynal, M., Stainer, J.: From wait-free to arbitrary concurrent solo executions in colorless distributed computing. Theor. Comput. Sci. **683**, 1-21 (2017)

28. Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM **46**(6), 858-923 (1999)

29. Hoest, G., Shavit, N.: Toward a topological characterization of asynchronous complexity. SIAM J. Comput. **36**(2), 457-497 (2006)

30. Imbs, D., Rajsbaum, S., Valle, A.: Untangling partial agreement: Iterated x-consensus simulations. In: 17th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), LNCS 9212, pp. 139-155. Springer (2015)

31. Kozlov, D.: Topology of the view complex. Homol. Homotopy Appl. **17**(1), 307-319 (2015)

32. Kuznetsov, P., Rieutord, T., He, Y.: An asynchronous computability theorem for fair adversaries. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC '18, pp. 387-396, Association for Computing Machinery, New York, NY, USA (2018)

33. Lynch, Nancy A.: A hundred impossibility proofs for distributed computing. In: 8th ACM Symposium on Principles of Distributed Computing (PODC), pp. 1-28 (1989)

34. Moses, Y., Rajsbaum, S.: A layered analysis of consensus. SIAM J. Comput. **31**(4), 989-1021 (2002)

35. Mostefaoui, A., Raynal, M., Tronel, F.: From binary consensus to multivalued consensus in asynchronous message-passing systems. Inf. Process. Lett. **73**(5-6), 207-212 (2000)

36. Rajsbaum, S.: Iterated shared memory models. In: López-Ortiz, Alejandro (ed), LATIN 2010: Theoretical Informatics, pp. 407-416. Springer Berlin Heidelberg, Berlin, Heidelberg (2010)

37. Raynal, M.: Fault-Tolerant Message-Passing Distributed Systems - An Algorithmic Approach. Springer, Cham (2018)

38. Rieutord, T.: Combinatorial characterization of asynchronous distributed computability. (Caractérisation combinatoire de la calculabilité distribuée asynchrone). PhD thesis, University of Paris-Saclay, France (2018)

39. Saks, M.E., Zaharoglou, F.: Wait-free *k*-set agreement is impossible: the topology of public knowledge. In: 25th ACM Symposium on Theory of Computing (STOC), pp. 101-110 (1993)

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.