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

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 \(\Pi =(\mathcal {I},\mathcal {O},\Delta )\) is defined by a collection \(\mathcal {I}\) of possible input configurations, a collection \(\mathcal {O}\) of possible output configurations, and a map \(\Delta :\mathcal {I}\rightarrow 2^{\mathcal {O}}\) specifying an input–output relation. A subset of processes starting with inputs as specified by a configuration \(\sigma \in \mathcal {I}\) must output values that define a configuration \(\tau \in \Delta (\sigma )\).

For our speedup theorem, we define the closure of a task \(\Pi \) with respect to a computational model M, denoted \(\textsf{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 \(\textsf{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 “\(\textsf{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 \(\textsf{CL} _M(\Pi )\) then depends on the nature of these objects. Intuitively, \(\textsf{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 \(\textsf{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 \(\textsf{CL} _M(\sigma )\).

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.

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.

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.

Bild vergrößern

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

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}\rightarrow 2^{\mathcal {O}}\) is an input–output specification. Every simplex \(\sigma =\{(i,x_i):i\in I\}\) of \(\mathcal {I}\), where \(I=\textsc {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 \(\textsc {id} (\tau )=\textsc {id} (\sigma )\) that are legal with respect to \(\sigma \). That is, assuming that only the processes in \(\textsc {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=\textsc {id} (\sigma )\subseteq [n]\), one round of communication performed by the processes in \(\textsc {id} (\sigma )\) as in Algorithm 1 results in various possible simplices, depending on the interleaving of the different write and read operations. Such a simplex is of the form \(\tau =\{(i,V_i):i\in I\}\), where \(V_i=\{(j,x_j):j\in J_i\}\) is the view of process i after one round. This view, or equivalently, the set \(J_i\subseteq I\), depends on the communication model M, i.e., write-collect, write-snapshot, or immediate snapshot. These simplices induces a complex, denoted by \(\mathcal {P}^{(1)}(\sigma )\), whose structure differs according to the three models considered on this paper. Figure 8 in Appendix B displays an example of these three different complexes, for a 2-dimensional simplex \(\sigma \) (i.e., a system with three processes). In the case of immediate snapshot, \(\mathcal {P}^{(1)}(\sigma )\) is the complex obtained by performing a chromatic subdivision of \(\sigma \) [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 bythe 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'_j):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)}\rightarrow \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.

In this section, we define the notion of a closure task (Fig. 2). As it will be shown later, given a computational model M, and given a task \(\Pi \), the closure of \(\Pi \) w.r.t. M, denoted by \(\textsf{CL} _M(\Pi )\), is a simpler task in the sense that if \(\Pi \) is solvable in t rounds in model M, then \(\textsf{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 \(\textsf{CL} _M(\Pi )\) and \(\Pi \) by taking the outputs of \(\textsf{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 \), \(\textsc {id} (v)\ne \textsc {id} (v')\). Intuitively, to every simplex \(\sigma \in \mathcal {I}\), and to every chromatic set of output vertices \(\tau \subseteq V(\mathcal {O})\) satisfying \(\textsc {id} (\tau ) =\textsc {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 \(\textsf{proj}_I(\mathcal {K})\) the subcomplex of \(\mathcal {K}\) induced by the vertices with IDs in I.

Bild vergrößern

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 '\).

We are now ready to define the closure task \(\textsf{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.

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 )\rightarrow \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'\).

Bild vergrößern

Since \({\Delta (\sigma )\subseteq \Delta '(\sigma )}\) for every \(\sigma \in \mathcal {I}\), the closure \(\textsf{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.

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.

The speedup theorem enables to provide short proofs for classical impossibility results or lower bounds, as illustrated below for consensus. A task \(\Pi =(\mathcal {I},\mathcal {O},\Delta )\) is said to be a fixed-point for model M whenever \(\textsf{CL} _M(\Pi )=\Pi \).

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}\) isThe 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.

We consider generic round-based algorithms in a model augmented with a black box object \(\textbf{B}\) as displayed in Algorithm 2. This algorithm is similar to Algorithm 1 except that a call to a black box \(\textbf{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 \(\textbf{B}_1,\dots ,\textbf{B}_t\) of \(\textbf{B}\), where \(\textbf{B}_r\) is the black box used by all processes at round r. Some of the black box objects we use have input and output values, hence before invoking \(\textbf{B}\) at a given round r, each process \(i\in [n]\) computes an input value \(a_i\) for \(\textbf{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 \(\textbf{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 \(\textbf{B}_r\), and the collection of the views of the other processes.

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.

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)}\rightarrow \mathcal {O}\) displayed on Fig. 4 is simplicial, and its composition with the map \(\Xi :\mathcal {I}\rightarrow \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 \(\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.

Bild vergrößern

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.

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

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

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

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.

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 \)

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

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

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 \(\textsf{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 consensus object, to which they all input the same value a, and from which they all get the same output \(b=a\). Hence, when only processes in S participate the closure of \(\epsilon \)-approximate agreement with respect to \(\beta \) is \((2\epsilon )\)-approximate agreement, as is the case without binary consensus object. We then repeat the same argument on S, by identifying a set \(S'\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 agreement task, until either the number of processes becomes very small or the precision parameter becomes very large, in which cases the task becomes easier. Therefore, the number of iterations of this reasoning is roughly \(\min \{\log _2 1/\epsilon ,\log _2n\}\). The exact figures are slightly more complicate because, for two processes, \(\epsilon \)-approximate agreement does not require at least \(\lceil \log _21/\epsilon \rceil \) rounds but \(\lceil \log _31/\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.

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