Brief Announcement: Asynchronous Approximate Agreement with Quadratic Communication

We consider a fully connected asynchronous network of $n$ message-passing parties $P_1,\mathrm{\dots },P_n$. Up to $t$ of these parties are corrupted in a byzantine manner, while the rest are honest.

In an approximate (convex) agreement problem, the parties output approximately equal values in the convex hull of their inputs. The most classical example is approximate agreement in $ℝ$, where the inputs/outputs are in $ℝ$, and for some parameter $\epsilon >0$ the following hold:

• $\mathrm{■}$

  validity: Each honest party output is between the minimum and maximum honest inputs.

• $\mathrm{■}$

  $𝜺$-agreement: If any honest parties $P_i$ and $P_j$ output $y_i$ and $y_j$, then $|y_i-y_j|\le \epsilon$.

Approximate agreement in $ℝ$ was introduced in 1985 by Dolev, Lynch, Pinter, Stark and Weihl [8]. Like byzantine agreement, in synchronous networks it is possible against faults with setup [12], but only possible when if the network is asynchronous [1] or if perfect (signature-free) security is desired [8]. What sets approximate agreement apart is that it is determinism-friendly. While deterministic byzantine agreement takes $t+1$ rounds in synchrony [7] and is impossible against just one crash in asynchrony [11], approximate agreement does not share these limitations. Thus, approximate agreement protocols are customarily deterministic.

In [8], Dolev et al. achieve $\epsilon$-agreement in $ℝ$ with a perfectly secure synchronous protocol secure against corruptions. Simplifying things slightly, in their protocol the parties estimate the spread $S$ of their inputs (the maximum difference between any two inputs), and run for $\lceil {\log }_2\frac{S}{\epsilon }\rceil$ rounds. In each round each party sends its value to every other party, and with this the parties halve the diameter of their values. After $\lceil {\log }_2\frac{S}{\epsilon }\rceil$ rounds, the spread is at most $2^{-\lceil {\log }_2(S/\epsilon )\rceil }\le \frac{\epsilon }{S}$ of what it initially was, and thus $\epsilon$-agreement is achieved. They present an asynchronous version of this protocol as well, but only with the resilience as the parties can no longer wait to receive the value of each honest party in every iteration.

Asynchronous approximate agreement in $ℝ$ with the optimal resilience was first achieved in 2004 by Abraham, Amit and Dolev [1], with a protocol that consists of $𝒪(\log \frac{S}{\epsilon })$ constant-round iterations. Each iteration involves one witness technique application where each party reliably broadcasts its current value in $ℝ$ (with a reliable broadcast protocol such as Bracha’s [5]), and obtains at least $n-t$ reliably broadcast values. The technique ensures that every two parties obtain the values of at least $n-t$ common parties. Since the technique’s introduction in [1], most asynchronous approximate agreement protocols have depended on it. Some examples are [1, 12] for agreement in $ℝ$, [14] for agreement in ${ℝ}^d$ when $d\ge 2$ and [15] for agreement in graphs (trees, chordal graphs, cycle-free semilattices). Note that this list is not exhaustive; we mention some other examples in the full version [10].

The witness technique requires the parties to reliably broadcast their inputs. Since reliable broadcast requires $\mathrm{\Omega }(n^2)$ messages for deterministic [9] or strongly adaptive [2] security against $t=\mathrm{\Omega }(n)$ faults, the witness technique requires $\mathrm{\Omega }(n^3)$ messages to be sent. Hence, the optimally resilient approximate agreement protocol of Abraham, Amit and Dolev [1] costs $\mathrm{\Theta }(n^3)$ messages per iteration. This is the case despite asynchronous approximate agreement being possible with $\mathrm{\Theta }(n^2)$ messages per iteration, as demonstrated by the protocol of Dolev et al. [8] which suboptimally tolerates faults. Therefore, we ask the following question: Is there an asynchronous approximate agreement protocol that optimally tolerates faults with only a quadratic (proportional to $n^2$) amount of communication?

In this work, we answer this question affirmatively by abandoning the witness technique. First, we achieve edge agreement (a discrete form of approximate agreement) in finite trees [15] with the optimal resilience via multivalued 2-graded consensus iterations. Then, we extend our protocol to achieve edge agreement in the infinite path $\mathbb{Z}$. Finally, we show that edge agreement in $\mathbb{Z}$ implies $\epsilon$-agreement in $ℝ$ by reducing the latter to the former. Our final protocol for $\epsilon$-agreement in $ℝ$ takes $6{\log }_2\frac{M}{\epsilon }+𝒪(\log \log \frac{M}{\epsilon })$ rounds (where $M$ is the maximum honest input magnitude), with $𝒪(n^2)$ messages of size $𝒪(\log \log \frac{M}{\epsilon })$ sent per round.

Our work is inspired by [13], which achieves exact convex agreement in $\mathbb{Z}$ with byzantine agreement iterations in a synchronous network. We instead achieve edge agreement in $\mathbb{Z}$ with graded consensus, which is much simpler than byzantine agreement, especially in asynchronous networks. Note though that [13] supports large inputs with less communication than us.

We consider an asynchronous network of $n$ message-sending parties $P_1,P_2,\mathrm{\dots },P_n$, fully connected via reliable and authenticated channels. An adversary corrupts up to parties, making them byzantine, and these parties become controlled by the adversary. The adversary adaptively chooses the parties it wants to corrupt during protocol execution, depending on the messages sent over the network. If a party is never corrupted, then we call it honest.

The parties do not have synchronized clocks. The adversary can schedule messages as it sees fit, and it is only required to eventually deliver messages with honest senders. If a party sends a message, then the adversary may corrupt the party instead of delivering the message.

To define asynchronous round complexity, we imagine an external clock. If a protocol runs in $R$ rounds, then the time elapsed between when every honest party running the protocol knows its input and when every honest party outputs/terminates is at most $R\mathrm{\Delta }$, where $\mathrm{\Delta }$ is the maximum honest message delay in the protocol’s execution.

Our first contribution is a protocol for edge agreement in finite trees. Against byzantine faults, this problem was first studied by Nowak and Rybicki [15]. It generalizes both edge agreement in finite paths (the discrete version of $\epsilon$-agreement in $[0,1]$) and graded consensus.

Nowak and Rybicki achieve edge agreement in a finite tree $T=(V,E)$ of diameter $D$ with $\lceil {\log }_{2}D\rceil +1$ constant-round witness technique iterations and thus $\mathrm{\Theta }(n^3\log D(\log |V|+\log n))$ bits of communication, where the $\log n$ term is due to the party IDs that identify each reliable broadcast’s sender party. Meanwhile, we achieve edge agreement with at most $h(T)$ iterations ($6h(T)+1$ rounds), where $h(T)$ ($T$’s centroid decomposition [16] height) is a property we define in the full version [10]. The integer value $h(T)$ can be anywhere in $[\lfloor {\log }_{2}D\rfloor ,\lceil {\log }_2|V|\rceil ]$, which means that our protocol’s round complexity is for some trees (though not for spider trees, trees with $𝒪(D)$ vertices etc.) worse than Nowak and Rybicki’s. However, our iterations only cost $𝒪(n^2)$ messages, each of size at most $𝒪(\log \mathrm{\Delta }+\log (h(T)))$ where $\mathrm{\Delta }$ is $T$’s maximum degree. So, our protocol requires roughly $n$ times less communication when $h(T)\approx {\log }_{2}D$.

In the full version [10], we present a parametrized recursive protocol $\mathrm{𝖳𝖢}(T)$ that achieves edge agreement in any given finite tree $T$. On a high level, it works as follows:

1. 1.

   If $T$ has 1 or 2 vertices, then each party outputs its input vertex. This is the base case.

2. 2.

   If $T$ has $s\ge 3$ vertices, then the parties let $\sigma$ be a centroid vertex of $T$ (whose deletion from $T$ results in a forest whose components all have at most $s/2$ vertices), and let $w_1,\mathrm{\dots },w_d$ be $\sigma$’s neighbors sorted by vertex index. Then, they run 2-graded consensus, where each party’s input is either $\sigma$ (if its edge agreement input is $\sigma$) or some neighbor $w_k$ of $\sigma$ (if its edge agreement input is in $H_k$, which is how we refer to the tree component of $T\setminus \{\sigma \}$ that contains $w_k$). If the parties reach consensus on $\sigma$, then they output $\sigma$. Otherwise, if they reach consensus on some neighbor $w_k$ of $\sigma$, then the parties with input vertices outside $H_k$ adopt the new input $w_k$, and we reduce the task to edge agreement in the subtree $H_k$.

There is a snag. The explanation above only works if the parties actually reach unanimous agreement on either $\sigma$ or on one of its neighbors $w_k$. However, 2-graded consensus does not guarantee this, since some parties might output $(\perp ,0)$ from it. What allows us to overcome this issue is that if anybody outputs $(\perp ,0)$, then the parties all learn that they ran 2-graded consensus with differing inputs, and thus learn that $\sigma$ is a safe output vertex w.r.t convex validity.

Our approach for finite trees above corresponds to binary search when the tree is a path. For example, the parties reach edge agreement in the path $(0,\mathrm{\dots },8)$ by either directly agreeing on $4$, or by reducing the problem to edge agreement in either $(0,\mathrm{\dots }3)$ or $(5,\mathrm{\dots },8)$. Binary search does not support the infinite path $\mathbb{Z}$. Fortunately, 2-graded consensus also enables exponential search. In the full version [10], we present a protocol for edge agreement in $\mathbb{Z}$ where we use 2-graded consensus to implement a strategy based on (doubly) exponential search.

When the maximum honest input magnitude is $M$, our protocol for edge agreement in $\mathbb{Z}$ takes $6{\log }_{2}M+𝒪(\log \log M)$ rounds, with $𝒪(n^2)$ messages of size $𝒪(\log \log M)$ per round. In the full version [10], we reduce $\epsilon$-agreement in $ℝ$ to edge agreement in $\mathbb{Z}$ to show that this implies $\epsilon$-agreement in $ℝ$ in $6{\log }_2\frac{M}{\epsilon }+𝒪(\log \log \frac{M}{\epsilon })$ rounds with $𝒪(n^2\log \frac{M}{\epsilon })$ messages and $𝒪(n^2\log \frac{M}{\epsilon }\log \log \frac{M}{\epsilon })$ bits of communication in total. Note that the factor 6 in the round complexity here stems from us using our 6-round 2-graded consensus protocol.

In terms of message and communication (though not round) complexity, our protocol for $\epsilon$-agreement in $ℝ$ is more efficient than that of Abraham et al. [1], who achieve $\epsilon$-agreement in $ℝ$ with $𝒪(\log \frac{S}{\epsilon })$ constant-round witness technique iterations (where $S$ is the honest input spread, i.e. the maximum difference of any honest inputs), and with $\mathrm{\Theta }(n^3\log \frac{S}{\epsilon })$ messages in total.

Another notable protocol is Delphi, by Bandarupalli, Bhat, Bagchi, Kate, Liu-Zhang and Reiter [4]. To efficiently achieve $\epsilon$-agreement with $\mathrm{\ell }$-bit inputs in $ℝ$, they assume an input distribution (normal distribution for the following), and when the honest input spread is $S$ they achieve $\epsilon$-agreement except with probability $2^{-\lambda }$ in $𝒪(\log (\frac{S}{\epsilon }\log \frac{S}{\epsilon })+\log (\lambda \log n))$ rounds with $𝒪(\mathrm{\ell }{n}^2\frac{S}{\epsilon }(\log (\frac{S}{\epsilon }\log \frac{D}{\epsilon })+\log (\lambda \log n)))$ bits of communication, while relaxing validity by allowing outputs outside the range of the honest inputs by at most $S$. They use the security parameter $\lambda$ here to assume bounds on $S$ that hold except with $2^{-\lambda }$ probability thanks to their input distribution assumptions. In comparison, we achieve $\epsilon$-agreement in $ℝ$ without relaxing validity or assuming any input bounds. As Table 1 shows, our protocol is also more efficient, in particular since Delphi requires a cubic amount of communication per round when $S\ge n\cdot \epsilon$.

In this section, we present a simplified $\epsilon$-agreement protocol that is better suited for a brief announcement than the more complicated full protocol in the full version [10]. While the full protocol uses 2-graded consensus, the simplified protocol in this section uses 3-graded consensus, which makes it less round-efficient since (with our graded consensus constructions) 3-graded consensus takes 9 rounds while 2-graded consensus takes 6. Moreover, the simplified protocol only supports inputs in bounded intervals rather than inputs in $ℝ$. Still, the protocols share the same core idea, which is that the parties repeatedly bisect the interval where their values reside by reaching graded consensus on whether their values are low or high.

In $\mathrm{𝖠𝗉𝗑}(a,b)$, the parameterized approximate agreement protocol we present in this section, the parties reach $\epsilon$-agreement in an interval $[a,b]$ by using 3-graded consensus to recursively reduce $\epsilon$-agreement in $[a,b]$ to $\epsilon$-agreement in either $[a,\frac{a+b}{2}]$ (reached via $\mathrm{𝖠𝗉𝗑}(a,\frac{a+b}{2})$) or $[\frac{a+b}{2},b]$ (reached via $\mathrm{𝖠𝗉𝗑}(\frac{a+b}{2},v)$). The parties reach 3-graded consensus on whether their inputs are below the midpoint $\frac{a+b}{2}$ or not. If they all have inputs below (resp. above) $\frac{a+b}{2}$, then they unanimously agree that this is the case, and so they run $\mathrm{𝖠𝗉𝗑}(a,\frac{a+b}{2})$ (resp. $\mathrm{𝖠𝗉𝗑}(\frac{a+b}{2},b)$) to reach approximate agreement. Otherwise, $\frac{a+b}{2}$ is in the honest input range, and this fact lets us assign an appropriate behavior to each 3-graded consensus output so that the parties reach approximate agreement no matter which two 3-graded consensus outputs they settle on.

When the parties run $\mathrm{𝖠𝗉𝗑}(0,1)$ for $\epsilon$-agreement in $[0,1]$, they reach the base case of a recursive $\mathrm{𝖠𝗉𝗑}(a,b)$ instance where $b-a\le \epsilon$ (where they can just output their inputs) with $\lceil {\log }_2\frac{1}{\epsilon }\rceil$ recursive $\mathrm{𝖠𝗉𝗑}$ calls, or in other words $\lceil {\log }_2\frac{1}{\epsilon }\rceil$ iterations of 3-graded consensus. In total, this costs $9\lceil {\log }_2\frac{1}{\epsilon }\rceil$ rounds, $𝒪(n^2\log \frac{1}{\epsilon })$ messages and $𝒪(n^2\log \frac{1}{\epsilon }\log \log \frac{1}{\epsilon })$ bits of communication. Here, we have a $\log \log \frac{1}{\epsilon }$ factor because the parties have to be able to tell to which 3-graded consensus iteration each message belongs to, and this requires $𝒪(\log \log \frac{1}{\epsilon })$-bit message tags.

Note that $\mathrm{𝖠𝗉𝗑}$ does not allow the parties to terminate (stop sending messages) after they output, since some parties not sending the messages they are supposed to send could lead to some other parties never obtaining outputs. We address this shortcoming in the full version [10] with a simple constant-round quadratic-complexity termination procedure.

If the parties all run $\mathrm{𝖠𝗉𝗑}(a,b)$ with inputs in $[a,\frac{a+b}{2})$, then each party $P_i$ runs ${\mathrm{𝖦𝖢}}_3$ with the input LEFT, outputs $(\text{LEFT},3)$ from ${\mathrm{𝖦𝖢}}_3$, and obtains its final output from an $\mathrm{𝖠𝗉𝗑}(a,\frac{a+b}{2})$ instance (that everybody runs) where its input is $v_i^{\mathrm{𝗇𝖾𝗑𝗍}}=v_i$. So, $\mathrm{𝖠𝗉𝗑}(a,b)$’s security recursively follows from $\mathrm{𝖠𝗉𝗑}(a,\frac{a+b}{2})$’s security. Likewise, if the parties all run $\mathrm{𝖠𝗉𝗑}(a,b)$ with inputs in $[\frac{a+b}{2},b]$, then they recursively reach $\epsilon$-agreement via $\mathrm{𝖠𝗉𝗑}(\frac{a+b}{2},b)$.

On the other hand, if neither $[a,\frac{a+b}{2})$ nor $[\frac{a+b}{2},b]$ contain all inputs, then $\frac{a+b}{2}$ is a safe output value w.r.t. validity. Knowing this, we can prove $\mathrm{𝖠𝗉𝗑}(a,b)$’s security via case analysis.

• $\mathrm{■}$

  If the parties all output $(\text{LEFT},3)$ or $(\text{LEFT},2)$ from ${\mathrm{𝖦𝖢}}_3$, then they all run $\mathrm{𝖠𝗉𝗑}(a,\frac{a+b}{2})$ with inputs in $[a,\frac{a+b}{2}]$ and obtain their outputs from it. So, security follows from $\mathrm{𝖠𝗉𝗑}(a,\frac{a+b}{2})$. Some parties (those with $\mathrm{𝖠𝗉𝗑}(a,b)$ inputs above $\frac{a+b}{2}$ and those with the ${\mathrm{𝖦𝖢}}_3$ grade $2$) run $\mathrm{𝖠𝗉𝗑}(a,\frac{a+b}{2})$ with the input $v_i^{\mathrm{𝗇𝖾𝗑𝗍}}=\frac{a+b}{2}$ instead of $v_i$. This is fine because $\frac{a+b}{2}$ is safe.

• $\mathrm{■}$

  If the parties all output $(\text{LEFT},2)$ or $(\text{LEFT},1)$ from ${\mathrm{𝖦𝖢}}_3$, then they all run $\mathrm{𝖠𝗉𝗑}(a,\frac{a+b}{2})$ with the input $\frac{a+b}{2}$, and thus all output $\frac{a+b}{2}$ from it. The parties with the ${\mathrm{𝖦𝖢}}_3$ grade $2$ output $\frac{a+b}{2}$ from $\mathrm{𝖠𝗉𝗑}(a,b)$ once they output this from $\mathrm{𝖠𝗉𝗑}(a,\frac{a+b}{2})$, while the ones with the ${\mathrm{𝖦𝖢}}_3$ grade $1$ output $\frac{a+b}{2}$ from $\mathrm{𝖠𝗉𝗑}(a,b)$ directly after they obtain the ${\mathrm{𝖦𝖢}}_3$ grade $1$.

• $\mathrm{■}$

  If the parties all output $(\text{LEFT},1)$ or $(\perp ,0)$ from ${\mathrm{𝖦𝖢}}_3$, then they all directly output $\frac{a+b}{2}$ from $\mathrm{𝖠𝗉𝗑}(a,b)$ after they output from ${\mathrm{𝖦𝖢}}_3$. Here, it does not matter that the parties with the ${\mathrm{𝖦𝖢}}_3$ grade $1$ run $\mathrm{𝖠𝗉𝗑}(a,\frac{a+b}{2})$ while the rest do not, because the parties with the ${\mathrm{𝖦𝖢}}_3$ grade $1$ do not care about their $\mathrm{𝖠𝗉𝗑}(a,\frac{a+b}{2})$ outputs.

• $\mathrm{■}$

  The cases where some parties obtain the ${\mathrm{𝖦𝖢}}_3$ value RIGHT are similar to the cases above.