Asynchronous Approximate Agreement with Quadratic Communication

Mizrahi Erbes, Mose; Wattenhofer, Roger

doi:10.4230/LIPIcs.OPODIS.2025.16

Asynchronous Approximate Agreement with Quadratic Communication

Mose Mizrahi Erbes

ETH Zurich, Switzerland Roger Wattenhofer

ETH Zurich, Switzerland

Abstract

We study approximate agreement in an asynchronous network of $n$ parties, up to $t$ of which are byzantine. This an agreement task where the parties obtain approximately equal inputs in the convex hull of their inputs. In an asynchronous network, it can be solved with the optimal resilience $t<\frac{n}{3}$ by forcing the parties to reliably broadcast their messages and thus preventing inconsistent byzantine behavior. This costs $\Theta(n^{2})$ messages per reliable broadcast, or $\Theta(n^{3})$ messages per protocol iteration.

In this work, we forgo reliable broadcast to achieve asynchronous approximate agreement against $t<\frac{n}{3}$ faults with quadratic communication. In a tree with the maximum degree $\Delta$ and the centroid decomposition height $h$ , we achieve edge agreement (agreement on two adjacent vertices) in at most $6h+1$ rounds with $\mathcal{O}(n^{2})$ messages of size $\mathcal{O}(\log\Delta+\log h)$ per round. We do this by designing a 6-round multivalued 2-graded consensus protocol and using it to construct a recursive edge agreement protocol. Then, we achieve edge agreement in the infinite path $\mathbb{Z}$ , again by using 2-graded consensus. Finally, we show that our edge agreement protocol enables approximate agreement in $\mathbb{R}$ (with outputs that are at most some small parameter $\varepsilon>0$ apart) in $6\log_{2}\frac{M}{\varepsilon}+\mathcal{O}(\log\log\frac{M}{\varepsilon})$ rounds with $\mathcal{O}(n^{2})$ messages of size $\mathcal{O}(\log\log\frac{M}{\varepsilon})$ per round, where $M$ is the maximum non-byzantine input magnitude.

Keywords and phrases:

Approximate agreement, byzantine fault tolerance, communication complexity

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Distributed algorithms

Editors:

Andrei Arusoaie, Emanuel Onica, Michael Spear, and Sara Tucci-Piergiovanni

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

We consider a fully connected asynchronous network of $n$ message-passing parties $P_{1},\dots,P_{n}$ . Up to $t$ of these parties suffer from byzantine faults, 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 $\mathbb{R}$ , where the inputs/outputs are in $\mathbb{R}$ , and for some parameter $\varepsilon>0$ the following hold:

$\blacksquare$

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

$\bm{\varepsilon}$ -agreement: If any honest parties $P_{i}$ and $P_{j}$ output $y_{i}$ and $y_{j}$ , then $|y_{i}-y_{j}|\leq\varepsilon$ .

Approximate agreement in $\mathbb{R}$ was introduced in 1985 by Dolev, Lynch, Pinter, Stark and Weihl [14]. Like byzantine agreement, in synchronous networks it is possible against $t<\frac{n}{2}$ faults with setup (public key infrastructure to enable message signing) [21], but only possible when $t<\frac{n}{3}$ if perfect (signature-free) security is desired [14] or the network is asynchronous. What sets approximate agreement apart is that it is determinism-friendly. While deterministic byzantine agreement takes $t+1$ rounds in synchrony [13] and is impossible against just one crash in asynchrony [17], approximate agreement does not share these limitations. Thus, approximate agreement protocols are customarily and preferably deterministic.

In [14], Dolev et al. achieved $\varepsilon$ -agreement in $\mathbb{R}$ with a perfectly secure synchronous protocol secure against $t<\frac{n}{3}$ 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}{\varepsilon}\rceil$ rounds. In each round each party sends its value to every other party, and this is enough for the parties to halve the spread of their values. After $\lceil\log_{2}\frac{S}{\varepsilon}\rceil$ rounds, the spread is at most $2^{-\lceil\log_{2}(S/\varepsilon)\rceil}\leq\frac{\varepsilon}{S}$ of what it initially was, and thus $\varepsilon$ -agreement is achieved. They presented an asynchronous version of this protocol as well, but only with the resilience $t<\frac{n}{5}$ as the parties can no longer wait to receive the value of each honest party in every iteration.

Asynchronous approximate agreement in $\mathbb{R}$ with the optimal resilience $t<\frac{n}{3}$ was first achieved by Coan in 1988 [10], who designed a simple protocol like the one above that tolerated $t<\frac{n}{3}$ crash faults, and then upgraded this simple protocol into a byzantine fault tolerant one. He obtained this upgrade by using Bracha’s reliable broadcast [8] to prevent the byzantine parties from transmitting different values to different parties, and by introducing a scheme to ensure that the parties ignore any values that could not have been sent by protocol-following parties. This upgrade has the drawback of turning the base protocol’s raw broadcasts into reliable broadcasts, causing a $\Theta(n)$ -fold communication increase as reliable broadcast requires $\Omega(n^{2})$ messages for deterministic [15] or strongly adaptive [2] security against $t=\Omega(n)$ faults. This means that the upgraded protocol costs $\Theta(n^{3})$ messages per iteration.

Later in 2004, Abraham, Amit and Dolev achieved a similar result: A cubic-complexity asynchronous protocol for approximate agreement in $\mathbb{R}$ with the optimal resilience $t<\frac{n}{3}$ . This protocol has an advantage over the previous ones: Its input spread estimation is fault tolerant, which means that its round complexity scales with the logarithm of the spread of only the honest parties’ inputs, rather than the spread of all inputs including the byzantine ones. Abraham et al. obtained this protocol by developing the witness technique, which involves each party reliably broadcasting a value and obtaining at least $n-t$ reliably broadcast values, with the guarantee that every two parties obtain the values of at least $n-t$ common parties. Since then, most asynchronous approximate agreement protocols have depended on this technique. Some examples are [1, 21] for agreement in $\mathbb{R}$ , [16, 22, 26] for agreement in $\mathbb{R}^{d}$ when $d\geq 2$ , and [11, 29] for agreement in graphs (trees, chordal graphs, cycle-free semilattices).

The optimally resilient protocols above cost $\Theta(n^{3})$ messages per round due to their use of reliable broadcast. However, asynchronous approximate agreement is possible with $\Theta(n^{2})$ messages per round, as shown by the protocol in [14] which tolerates $t<\frac{n}{5}$ faults. So, we ask: Is there an asynchronous approximate agreement protocol that optimally tolerates $t<\frac{n}{3}$ faults with only a quadratic (proportional to $n^{2}$ ) amount of communication?

In this work, we answer this question affirmatively by forgoing reliable broadcast. First, we achieve edge agreement in finite trees [29] (agreement on two adjacent vertices) with the optimal resilience $t<\frac{n}{3}$ via multivalued 2-graded consensus iterations. Then, we extend our protocol to achieve edge agreement in the infinite path $\mathbb{Z}$ . Finally, we achieve $\varepsilon$ -agreement in $\mathbb{R}$ by reducing it to edge agreement in $\mathbb{Z}$ . Our final protocol for $\varepsilon$ -agreement in $\mathbb{R}$ takes $6\log_{2}\frac{M}{\varepsilon}+\mathcal{O}(\log\log\frac{M}{\varepsilon})$ rounds (where $M$ is the maximum honest input magnitude) with $\mathcal{O}(n^{2})$ messages of size $\mathcal{O}(\log\log\frac{M}{\varepsilon})$ sent per round, which means that its total communication complexity is quadratic in $n$ . Note that we do not require the parties to know $M$ in advance for this.

Our work is inspired by [23], which achieves exact convex agreement in $\mathbb{Z}$ (on a single integer) with byzantine agreement iterations in a synchronous network. We instead achieve edge agreement in $\mathbb{Z}$ (on two adjacent integers) with iterations of graded consensus, which is a much simpler primitive than byzantine agreement, especially in asynchronous networks.

2 Model & Definitions

We consider an asynchronous network of $n$ message-sending parties $P_{1},P_{2},\dots,P_{n}$ which are fully connected via reliable and authenticated channels. An adversary corrupts up to $t<\frac{n}{3}$ parties, making them byzantine, and it takes control of these parties. The adversary adaptively chooses the parties it wants to corrupt during protocol execution, depending on the parties’ internal states and all sent messages. 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.

We say that a party multicasts $m$ when it sends $m$ to every party. By corrupting a party that is multicasting a message, the adversary may deliver the message to only some parties.

Our protocols are live; i.e., they achieve liveness. That is, if the honest parties all acquire inputs and all run forever, then they all output. However, in Section 6, we explain a low-cost way to upgrade our live protocols into terminating versions that allow the parties to halt.

To define asynchronous round complexity, we imagine an external clock. If a protocol runs in $R$ rounds, then it is live or terminating, and 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\Delta$ , where $\Delta$ is the maximum honest message delay in the protocol’s execution. Note that this definition matches the notion defined as “time complexity” in [4].

Edge Agreement in a Tree

In edge agreement in a tree graph $T=(V,E)$ , each party $P_{i}$ acquires an input vertex $v_{i}\in V$ , and outputs a vertex $y_{i}\in V$ . We want the following properties:

$\blacksquare$

edge agreement: Every two honest output vertices are either equal or adjacent in $T$ .
$\blacksquare$

convex validity: For every honest output $y$ , there exist some (possibly equal) honest inputs $v_{y}$ and $v^{\prime}_{y}$ such that $y$ is on the path which connects $v_{y}$ and $v^{\prime}_{y}$ in $T$ .

Edge agreement in a tree generalizes edge agreement in a path, which is essentially the same task as approximate agreement in an interval in $\mathbb{R}$ , but with the input/output domain restricted to the integers (with adjacent integers representing adjacent path vertices).

Graded Consensus

In $k$ -graded consensus, each party $P_{i}$ acquires an input $v_{i}$ in an input domain $\mathcal{M}$ , and outputs some value-grade pair $(y_{i},g_{i})\in(\mathcal{M}\times\{1,\dots,k\})\cup\{(\bot,0)\}$ . The following must hold:

$\blacksquare$

agreement: If any honest parties $P_{i}$ and $P_{j}$ output $(y_{i},g_{i})$ and $(y_{j},g_{j})$ , then $|g_{i}-g_{j}|\leq 1$ , and if $\min(g_{i},g_{j})\geq 1$ , then $y_{i}=y_{j}$ .
$\blacksquare$

intrusion tolerance: If $(y,g)\neq(\bot,0)$ is an honest output, then $y$ is an honest input.
$\blacksquare$

validity: If the honest parties have a common input $m\in\mathcal{M}$ , then they all output $(m,k)$ .

Figure 1: Observe that

k

-graded consensus with the input domain

\mathcal{M}

is the same problem as edge agreement in the spider tree with the center

(\bot,0)

and the path

((m,1),\dots,(m,k))

attached to it for each

m\in\mathcal{M}

when the parties can only have the tree’s leaves as edge agreement inputs, with each leaf input

(m,k)

in bijection with the

k

-graded consensus input

m

[4]. Note that this equivalence requires intrusion tolerance, which some works (e.g. [9]) do not include as a graded consensus property.

In this work, we use both binary 2-graded consensus (with $|\mathcal{M}|=2$ ) and multivalued 2-graded consensus (with $|\mathcal{M}|>2$ ). For the latter, there is a 9-round protocol in the literature that costs $\mathcal{O}(n^{2})$ messages of size $\mathcal{O}(\log|\mathcal{M}|)$ [4]. This protocol is enough for our asymptotic complexity results. However, it achieves a property called binding [4] that we do not need, and without this property, 6 rounds suffice. We show this in the appendix by constructing a family of multivalued $2^{k}$ -graded consensus protocols $\mathsf{GC}_{2^{0}},\mathsf{GC}_{2^{1}},\mathsf{GC}_{2^{2}},\mathsf{GC}_{2^{3}% },\dots$ which each take $3k+3$ rounds, with $\mathcal{O}(n^{2})$ messages of size $\mathcal{O}(\log k+\log|\mathcal{M}|)$ per round. We obtain this family by constructing a $1$ -graded consensus protocol $\mathsf{GC}_{1}$ , and by repeatedly grade-doubling it.¹¹1Repeated grade-doubling is a standard method to achieve $2^{k}$ -graded consensus in $\mathcal{O}(k)$ rounds [18, 5, 25], though note that synchronous networks allow $k^{k}$ -graded consensus in $\mathcal{O}(k)$ rounds [20].

3 Overview & Contributions

Our first contribution is a new protocol for edge agreement in finite trees. Against byzantine faults, this problem was first studied by Nowak and Rybicki [29]. It generalizes both edge agreement in finite paths (the discrete version of $\varepsilon$ -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 $\Theta(n^{3}\log D(\log|V|+\log n))$ bits of communication, where the $\log n$ term arises from the party ID values that identify each witness technique reliable broadcast’s sender party. Meanwhile, we achieve edge agreement in at most $6h(T)+1$ rounds, where $h(T)$ is a property which we formally define in Section 4 as the maximum of the heights of $T$ ’s centroid decompositions [30]. 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 $\mathcal{O}(D)$ vertices such as paths etc.) worse than Nowak and Rybicki’s. However, our rounds only cost $\mathcal{O}(n^{2})$ messages, each of size at most $\mathcal{O}(\log\Delta+\log(h(T)))$ where $\Delta$ is $T$ ’s maximum degree. So, our protocol requires roughly $n$ times less communication when $h(T)\approx\log_{2}D$ .

In Section 4, we present a parametrized recursive protocol $\mathsf{TC}(T)$ for edge agreement in a given finite tree $T$ . On a high level, it works as follows:

1.

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

If $T$ has $s\geq 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},\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 one of its neighbors $w_{k}$ . However, 2-graded consensus does not guarantee this, as some parties might output $(\bot,0)$ from it. What allows us to overcome this issue is that if anybody outputs $(\bot,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.

Table 1: Comparison of protocols for asynchronous

\varepsilon

-agreement in

\mathbb{R}

when the parties have inputs in

[0,1]

. If

v_{\mathsf{lo}}

and

v_{\mathsf{hi}}

are the minimum and maximum honest inputs, then

S=v_{\mathsf{hi}}-v_{\mathsf{lo}}

and

M=v_{\mathsf{hi}}

. To simplify the comparisons, we assume for [14], [10], [1] and [5] that the inputs are multiples of

\varepsilon

.

Threshold	Bits Sent / Round	Round Complexity^a	Relaxation^b	Source
$t<\frac{n}{5}$	$\mathcal{O}(n^{2}\log\frac{1}{\varepsilon})$	$\mathcal{O}(\log\frac{1}{\varepsilon})$	0	[14]
$t<\frac{n}{3}$	$\mathcal{O}(n^{3}\log\frac{n}{\varepsilon})$	$\mathcal{O}(\log\frac{1}{\varepsilon})$	0	[10]
$t<\frac{n}{3}$	$\mathcal{O}(n^{3}\log\frac{n}{\varepsilon})$ ^c	$\mathcal{O}(\log\frac{S}{\varepsilon})$	0	[1]
$t<\frac{n}{3}$	$\mathcal{O}(n^{2}\min(\frac{S}{\varepsilon},n\log\frac{1}{\varepsilon}))$	$\mathcal{O}(\log(\frac{\log(1/\varepsilon)\min(1/\varepsilon,n)}{\varepsilon}))$	$S$	[5]
$t<\frac{n}{3}$	$\mathcal{O}(n^{2}\log\log\frac{M}{\varepsilon})$ ^d	$\mathcal{O}(\log\frac{M}{\varepsilon})$	0	this work

a

The round complexities of [14] and [10] depend on the spread of all inputs, including byzantine ones. In the domain $[0,1]$ , this spread is at most $1$ , which gives us the round complexity $\mathcal{O}(\log\frac{1}{\varepsilon})$ .
b

The relaxation is how far an honest output is allowed to be from the honest input range $[v_{\mathsf{lo}},v_{\mathsf{hi}}]$ .
c

The first few rounds of [1] estimate the spread $S$ , and this costs $\Theta(n^{4}\log\frac{1}{\varepsilon})$ bits of communication. However, this can be reduced to $\Theta(n^{3}\log\frac{n}{\varepsilon})$ with modern reliable broadcast protocols [3].
d

The $\log\log\frac{M}{\varepsilon}$ factor here is for tags that distinguish messages sent in different protocol iterations.

Our approach for finite trees corresponds to binary search when the tree is a path. For example, the parties reach edge agreement in the path $(0,\dots,8)$ by either directly agreeing on $4$ , or by reducing the problem to edge agreement in either $(0,\dots 3)$ or $(5,\dots,8)$ .

Binary search does not support the infinite path $\mathbb{Z}$ . Fortunately, 2-graded consensus also enables exponential search. In Section 5, we present a protocol for edge agreement in $\mathbb{Z}$ that on a high level works as follows (with some complications that we skip over for now due to our use of 2-graded consensus instead of byzantine agreement).

1.

First, the parties reach 2-graded consensus on whether they prefer to agree on the left path $(\dots,-1,0)$ or the right path $\mathbb{N}=(0,1,\dots)$ , with each party preferring $\mathbb{N}$ iff its input is in $\mathbb{N}$ . Below, we explain what the parties then do if they decide to agree in $\mathbb{N}$ . Otherwise, they follow the same steps, but with mirrored (sign-flipped) inputs and outputs.
2.

The parties run exponential search with the phases $k=0,1,\dots$ ; where in each phase $k$ they reach 2-graded consensus on if they have inputs in the left path $(2^{k}-1,\dots,2^{k+1}-1)$ or the right path $(2^{k+1},\dots)$ . If they decide on the left path, then they reach edge agreement in it using our protocol for edge agreement in finite trees. Otherwise, if they decide on the right path, then they increment the phase counter $k$ and continue exponential search.
3.

Instead of directly using exponential search for edge agreement in $\mathbb{N}$ , we take inspiration from [6], and design a two-stage protocol that is asymptotically twice as round-efficient. Roughly speaking, the parties run the protocol we described above based on exponential search to approximately agree on some $k$ such that the path $(2^{k}-1,\dots,2^{k+1}-1)$ contains safe output values w.r.t. convex validity, and then they reach edge agreement in this path.

When the maximum honest input magnitude is $M$ (when the honest input that is most distant from $0$ is either $M$ or $-M$ ), our protocol for edge agreement in $\mathbb{Z}$ takes $6\log_{2}M+\mathcal{O}(\log\log M)$ rounds, with $\mathcal{O}(n^{2})$ messages of size $\mathcal{O}(\log\log M)$ per round. In Section 7, we reduce $\varepsilon$ -agreement in $\mathbb{R}$ to edge agreement in $\mathbb{Z}$ to show that this implies $\varepsilon$ -agreement in $\mathbb{R}$ in $6\log_{2}\frac{M}{\varepsilon}+\mathcal{O}(\log\log\frac{M}{\varepsilon})$ rounds with $\mathcal{O}(n^{2}\log\frac{M}{\varepsilon})$ messages and $\mathcal{O}(n^{2}\log\frac{M}{\varepsilon}\log\log\frac{M}{\varepsilon})$ bits of communication in total. Note that factor 6 in the round complexity here is due to us using our 6-round 2-graded consensus protocol. If for any other $r$ we used a $r$ -round protocol instead, like the 2-round 2-graded consensus protocol in [4] that tolerates $t<\frac{n}{5}$ faults, then this factor would be $r$ instead.

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

Another notable protocol is Delphi, by Bandarupalli, Bhat, Bagchi, Kate, Liu-Zhang and Reiter [5]. To efficiently achieve $\varepsilon$ -agreement with $\ell$ -bit inputs in $\mathbb{R}$ , they assume an input distribution (normal distribution for the following), and when the honest input spread is $S$ they achieve $\varepsilon$ -agreement in $\mathcal{O}(\log(\frac{S}{\varepsilon}\log\frac{S}{\varepsilon})+\log(\lambda% \log n))$ rounds with $\mathcal{O}(\ell n^{2}\frac{S}{\varepsilon}(\log(\frac{S}{\varepsilon}\log% \frac{S}{\varepsilon})+\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 parameter $\lambda$ here to assume bounds on the honest inputs that hold except with a probability negligible in $\lambda$ , and allow their protocol to fail if these bounds are violated. In comparison, we achieve $\varepsilon$ -agreement in $\mathbb{R}$ 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\geq n\cdot\varepsilon$ .

4 Edge Agreement in a Tree

In $\mathbb{R}^{d}$ , a set $Z\subseteq\mathbb{R}^{d}$ is straight-line convex if for all $z_{1},z_{2}\in Z$ it contains the line segment (the shortest path in $\mathbb{R}^{d}$ ) that connects $z_{1}$ and $z_{2}$ . This definition translates to convexity on a tree $T=(V,E)$ , where a set $Z\subseteq V$ is convex if for all $z_{1},z_{2}\in Z$ the set $Z$ contains all the vertices on the shortest path (the only path) between $z_{1}$ and $z_{2}$ [29, 11]. Hence, we can define convex hulls on $T$ , where the convex hull $\langle Z\rangle$ of any vertex set $Z\subseteq V$ is the set that consists of the vertices in $Z$ and every other vertex $v\in V$ that is on the path between some $z_{1},z_{2}\in Z$ .

For edge agreement, the convex validity property is that when the honest parties have the set of inputs $X$ , they obtain outputs in $\langle X\rangle$ . To achieve this, we rely on the following fact:

Proposition 1.

For every tree $T=(V,E)$ , $Z\subseteq V$ and $Y\subseteq\langle Z\rangle$ it holds that $\langle Y\rangle\subseteq\langle Z\rangle$ .

Proof.

Observe that for any tree $T=(V,E)$ and any $Z\subseteq V$ , the graph $T[\langle Z\rangle]$ (the subgraph of $T$ induced by $\langle Z\rangle$ ) is a connected union of paths from $T$ , which makes $T[\langle Z\rangle]$ a tree itself. For any $Y\subseteq\langle Z\rangle$ , the tree $T[\langle Z\rangle]$ contains every $y_{1},y_{2}\in Y$ , and as $T[\langle Z\rangle]$ is a tree it also contains the path which connects $y_{1}$ and $y_{2}$ . That is, $T[\langle Z\rangle]$ contains every vertex in $\langle Y\rangle$ . $\hfill\blacktriangleleft$

Every finite tree $T$ has a set of centroid vertices (either one vertex or two adjacent ones) such that if one deletes a centroid vertex $\sigma$ from $T$ , then every component tree of the resulting forest $T\setminus\{\sigma\}$ has at most half as many vertices as $T$ [24, 30]. For any finite tree $T$ , one can recursively define a centroid decomposition of $T$ to be a rooted tree $T^{\prime}$ with the following properties (helpfully visualized in [30]):

$\blacksquare$

The root of $T^{\prime}$ is a centroid vertex $\sigma$ of $T$ .
$\blacksquare$

If in $T$ the centroid $\sigma$ has exactly $d$ neighbors $w_{1},\dots,w_{d}$ for any $d\geq 0$ , then in $T^{\prime}$ the root $\sigma$ has exactly $d$ child subtrees $W_{1},\dots,W_{d}$ , such that for all $k\in\{1,\dots,d\}$ the subtree $W_{k}$ is a centroid decomposition of the tree component that contains $w_{k}$ in the forest $T\setminus\{\sigma\}$ .

Finally, let us define the centroid decomposition height $h(T)$ of a finite tree $T=(V,E)$ to be the maximum height of any centroid decomposition of $T$ . The recursive definition of a centroid decomposition above allows one to prove by induction that $h(T)\leq\lceil\log_{2}|V|\rceil$ (where $|V|$ is the number of vertices), and this bound is tight if $T$ is a path and $|V|$ is a power of $2$ . However, there are trees that have low centroid decomposition heights despite having many vertices. For example, if $T$ is a star, then $h(T)=1$ no matter how many vertices $T$ has, as removing a star’s unique centroid (its center vertex) leaves behind a forest of isolated vertices.

Below, we present a recursive protocol $\mathsf{TC}(T)$ based on centroid decomposition for edge agreement in a finite tree $T$ . If $T$ has at most two vertices, then each party $P_{i}$ just outputs its input vertex. Otherwise, the parties let $\sigma$ be the minimum-index centroid of $T$ , and run our 2-graded consensus protocol $\mathsf{GC}_{2}$ to either directly output $\sigma$ , or to reduce edge agreement in $T$ to edge agreement in a component tree $T^{\prime}$ of $T\setminus\{\sigma\}$ , handled with a recursive $\mathsf{TC}(T^{\prime})$ instance. The recursion depth is at most $h(T)$ since each recursive call represents a step from a vertex to its child in a centroid decomposition of $T$ whose height is upper bounded by $h(T)$ .

The idea behind $\mathsf{TC}(T)$ when $T$ has $3$ or more vertices is that either there is a component $H_{k}$ of $T\setminus\{\sigma\}$ that contains every honest input vertex $v_{i}$ , or there is no such component.

$\blacksquare$

In the former case where there is such a component, every honest party $P_{i}$ runs $\mathsf{GC}_{2}$ with the input $k$ , outputs $(k,2)$ from it, lets $(v_{i}^{\mathsf{next}},T_{i}^{\mathsf{next}})=(v_{i},H_{k})$ , and obtains its final output from a recursive $\mathsf{TC}(H_{k})$ instance which it runs with the input $v_{i}^{\mathsf{next}}=v_{i}$ . Thus, edge agreement in $T$ is reduced to edge agreement in $H_{k}$ , which the parties reach via $\mathsf{TC}(H_{k})$ .
$\blacksquare$

In the latter case where there is no such component, there are some honest inputs $v_{i}$ and $v_{j}$ such that either $\sigma\subseteq\{v_{i},v_{j}\}$ or $v_{i}$ and $v_{j}$ are in different components of $T\setminus\{\sigma\}$ . So, $\sigma$ is on the path which connects $v_{i}$ and $v_{j}$ in $T$ , which makes it a safe output vertex w.r.t. convex validity. Moreover, if some honest party $P_{i}$ outputs $(k,g)$ from $\mathsf{GC}_{2}$ for some $k\not\in\{\bot,0\}$ and either $g=1$ or $P_{i}$ ’s $\mathsf{TC}(T)$ input $v_{i}$ is not in $H_{k}$ , then some but not all of the honest parties have inputs in $H_{k}$ , which means that $w_{k}$ is a safe output vertex w.r.t. convex validity as it is incident to the edge that connects $H_{k}$ with the rest of the tree. With these in mind, we assign each $\mathsf{GC}_{2}$ output a behavior such that no matter which two adjacent $\mathsf{GC}_{2}$ outputs the parties settle on, they behave in a compatible manner that leads to edge agreement.

Figure 2: Let

T

be the tree depicted above with the unique centroid

\sigma

and the subtrees

H_{1}

,

H_{2}

,

H_{3}

(the components of

T\setminus\{\sigma\}

). If the parties run

\mathsf{TC}(T)

, then each party with the input

\sigma

runs

\mathsf{GC}_{2}

with the input

0

, and each party

P_{i}

with an input

v_{i}\neq\sigma

lets its

\mathsf{GC}_{2}

input be the index

k\in\{1,2,3\}

such that

v_{i}\in H_{k}

. If for some

k\in\{1,2,3\}

every input

v_{i}

is in

H_{k}

, then the parties all run

\mathsf{GC}_{2}

with the input

k

and thus output

(k,2)

from it. Otherwise,

\sigma

is in the convex hull of the input vertices

v_{i}

.

Theorem 2.

For any finite tree $T$ , suppose the honest parties run $\mathsf{TC}(T)$ with input vertices in $T$ . Then, they reach edge agreement in $T$ based on their input vertices in at most $6h(T)$ rounds if they have a common input vertex, and in at most $6h(T)+1$ rounds otherwise.

Proof.

Below, we show for any finite tree $T$ that if $\mathsf{TC}(H)$ works well (in accordance with the theorem) for every tree $H$ such that $h(H)<h(T)$ , then $\mathsf{TC}(T)$ also works well. So, by strong induction on $h(T)$ , $\mathsf{TC}(T)$ works well for every finite tree $T$ , no matter what $h(T)\geq 0$ is.

In the base case where $T$ has at most $2$ vertices, the parties reach edge agreement in $0$ rounds by outputting their inputs. This is what happens when $h(T)=0$ , as $h(T)=0$ iff $T$ is a vertex. For the rest of the proof, suppose $T$ has at least $3$ vertices, which implies $h(T)\geq 1$ .

Let $\sigma$ be the minimum-index centroid vertex of $T$ with the neighbors $w_{1},\dots,w_{d}$ sorted by vertex index, and let $H_{1},\dots,H_{d}$ be the corresponding tree components of $T\setminus\{\sigma\}$ such that $H_{j}$ contains $w_{j}$ for all $j$ . Observe that $h(T)$ is greater than $h(H_{j})$ for all $j$ , as $T$ has some centroid decomposition rooted at $\sigma$ , with $d$ child subtrees $W_{1},\dots,W_{d}$ attached to $\sigma$ where each subtree $W_{j}$ is a centroid decomposition of $H_{j}$ of height $h(H_{j})$ . So, our inductive assumption tells us that $\mathsf{TC}(H_{j})$ works well for all $j\in\{1,\dots,d\}$ .

First, let us consider the simpler scenario, which is when there exists some $k\in\{1,\dots d\}$ such that the subtree $H_{k}$ contains every honest input vertex. In this scenario, the honest parties all run $\mathsf{GC}_{2}$ with the input $k$ , and thus all output $(k,2)$ from it. Then, each honest party $P_{i}$ sets $(v_{i}^{\mathsf{next}},T_{i}^{\mathsf{next}})=(v_{i},H_{k})$ , runs a common instance of $\mathsf{TC}(T_{i}^{\mathsf{next}})=\mathsf{TC}(H_{k})$ with the other parties where its input is $v_{i}^{\mathsf{next}}=v_{i}$ , and obtains its final output from this recursive $\mathsf{TC}(H_{k})$ instance. Therefore, edge agreement in $T$ follows from edge agreement in $H_{k}$ , which the parties reach via $\mathsf{TC}(H_{k})$ . The round complexity of $\mathsf{TC}(T)$ here is at most that of $\mathsf{GC}_{2}$ and $\mathsf{TC}(H_{k})$ added together; which is always at most $6+6h(H_{k})+1\leq 6h(T)+1$ , and is at most $6+6h(H_{k})\leq 6h(T)$ if the honest parties run $\mathsf{TC}(T)$ (and thus $\mathsf{TC}(H_{k})$ ) with a common input. Note that the honest parties do not output $\sigma$ on Line 21 in this scenario since none of them obtain the grade $0$ from $\mathsf{GC}_{2}$ , which means that none of them multicast CENTER and thus that none of them receive the message CENTER from $t+1$ parties.

Now, let us consider the more complicated scenario where none of the subtrees $H_{1},\dots,H_{d}$ contains every honest input vertex. Then, there exist some distinct honest inputs $v_{i}$ and $v_{j}$ such that either $\sigma\in\{v_{i},v_{j}\}$ , or $v_{i}$ and $v_{j}$ are in different components of $T\setminus\{\sigma\}$ . In either case, $\sigma$ is on the path that connects $v_{i}$ and $v_{j}$ in $T$ , which means that $\sigma$ is in the convex hull of the honest inputs. In addition, if for some $k\in\{1,\dots,d\}$ an honest party $P_{i}$ outputs $(k,g)$ from $\mathsf{GC}_{2}$ and either $g=1$ or $P_{i}$ ’s input $v_{i}$ is not in $H_{k}$ , then some but not all of the honest parties have inputs in $H_{k}$ (the “some” part by $\mathsf{GC}_{2}$ ’s intrusion tolerance and the “not all” part by either $P_{i}$ ’s grade being below $2$ or by $P_{i}$ ’s input not being in $H_{k}$ ), and this places $w_{k}$ inside the convex hull of the honest inputs since $w_{k}$ is on every path in $T$ that connects the honest inputs in $H_{k}$ with the honest inputs outside $H_{k}$ . With these in mind, let us consider all the ways a $\mathsf{TC}(T)$ execution can go, depending on the honest parties’ $\mathsf{GC}_{2}$ outputs.

$\blacksquare$

It could happen that the honest parties all output $(k,2)$ or $(k,1)$ from $\mathsf{GC}_{2}$ for some $k\in\{1,\dots,d\}$ , with at least one outputting $(k,2)$ . This situation is similar to the one we considered previously, except for the fact that some honest parties $P_{i}$ (those with inputs outside $H_{k}$ and those with the $\mathsf{GC}_{2}$ grade $1$ ) set $v_{i}^{\mathsf{next}}=w_{k}$ instead of setting $v_{i}^{\mathsf{next}}=v_{i}$ . By Proposition 1, them doing this does not impact convex validity, as the convex hull $\langle V\rangle$ of the honest $\mathsf{TC}(T)$ input vertices $V=\bigcup_{P_{i}\text{ is honest}}\{v_{i}\}$ is a superset of the convex hull of $\{w_{k}\}\cup V\subseteq\langle V\rangle$ . So, edge agreement in $T$ follows from edge agreement in $H_{k}$ (in at most $6+6h(H_{k})+1\leq 6h(T)+1$ rounds), because after running $\mathsf{GC}_{2}$ , the honest parties all run $\mathsf{TC}(H_{k})$ with safe inputs in $H_{k}$ and all obtain their final outputs from $\mathsf{TC}(H_{k})$ . Again in this case, the parties do not output $\sigma$ on Line 21 since none of them multicast CENTER.
$\blacksquare$

It could happen that the honest parties all obtain $\mathsf{GC}_{2}$ outputs in $\{(\bot,0),(0,1),(0,2)\}$ . Then, every honest party outputs $\sigma$ , either directly on Line 9 or Line 15 after outputting from $\mathsf{GC}_{2}$ , or even earlier by receiving $t+1$ CENTER messages. In either case, the honest parties reach exact agreement on the safe vertex $\sigma$ , in at most $6\leq 6h(T)+1$ rounds.
$\blacksquare$
Finally, it could happen that the honest parties all output $(k,1)$ or $(\bot,0)$ from $\mathsf{GC}_{2}$ for some $k\in\{1,\dots,d\}$ , with at least one outputting $(k,1)$ . Then, every honest party $P_{i}$ that runs $\mathsf{TC}(T_{i}^{\mathsf{next}})$ does so with the tree $T_{i}^{\mathsf{next}}$ set to $H_{k}$ and with the input vertex $v_{i}^{\mathsf{next}}=w_{k}$ . For the honest parties that output $(k,1)$ from $\mathsf{GC}_{2}$ , this follows from Line 11 and Line 12. Meanwhile, for an honest party that outputs $(\bot,0)$ and thus sets $(v_{i}^{\mathsf{next}},T_{i}^{\mathsf{next}})=(w_{k^{\prime}},H_{k^{\prime}})$ on Line 17 upon receiving the message $(\texttt{KVAL},k^{\prime})$ from $t+1$ parties; this follows from $k^{\prime}$ being equal to $k$ due to every honest KVAL message being on $k$ and this making $k$ the only value on which a party can receive $t+1$ KVAL messages. From all of these, we conclude that the honest parties can only output the safe vertex $\sigma$ (on Line 15 or 21), or output $\sigma$ ’s safe neighbor $w_{k}$ after outputting $w_{k}$ from $\mathsf{TC}(H_{k})$ , which the honest parties can only run with the input $w_{k}$ . It remains to show liveness. Observe that since $n-t\geq 2t+1$ , either $t+1$ honest parties output $(\bot,0)$ from $\mathsf{GC}_{2}$ , or $t+1$ honest parties output $(k,1)$ from $\mathsf{GC}_{2}$ .
- –
  
  If the former happens, then $t+1$ honest parties multicast CENTER after outputting $(\bot,0)$ from $\mathsf{GC}_{2}$ . Hence, after one round following $\mathsf{GC}_{2}$ (i.e. $7\leq 6h(T)+1$ rounds after $\mathsf{TC}(T)$ begins), every honest party becomes able to output $\sigma$ on Line 21.
- –
  
  If the latter happens, then $t+1$ honest parties multicast $\langle{\texttt{KVAL}},{k}\rangle$ after outputting $(k,1)$ from $\mathsf{GC}_{2}$ . So, after one round following $\mathsf{GC}_{2}$ (i.e. $7\leq 6h(T)+1$ rounds after $\mathsf{TC}(T)$ begins), the honest parties all learn $k$ and start running $\mathsf{TC}(H_{k})$ with the common input $w_{k}$ . Every honest party outputs $w_{k}$ from $\mathsf{TC}(H_{k})$ once $7+6h(H_{k})\leq 6h(T)+1$ rounds have passed, and thus outputs $\sigma$ or $w_{k}$ from $\mathsf{TC}(T)$ in at most $6h(T)+1$ rounds.

$\hfill\blacktriangleleft$

Complexity of $\mathsf{TC}(T)$ .

The round complexity of $\mathsf{TC}(T)$ is at most $6h(T)+1$ , by Theorem 2. If $T$ ’s maximum degree is $\Delta$ , then in each of $\mathsf{TC}(T)$ ’s at most $h(T)$ recursive iterations the $\mathsf{GC}_{2}$ instance is run with inputs in $\{0,1,\dots,\Delta\}$ and the KVAL messages carry values in $\{1,\dots,\Delta\}$ . This means that each iteration costs $\mathcal{O}(n^{2})$ messages, each of size at most $\mathcal{O}(\log\Delta+\log(h(T)))$ , where the $\log(h(T))$ term is due to the iteration ID tags which distinguish different iterations’ messages from each other. So, $\mathsf{TC}(T)$ ’s total message complexity is $\mathcal{O}(n^{2}h(T))$ , and its total communication complexity is $\mathcal{O}(n^{2}h(T)(\log\Delta+\log(h(T))))$ bits. Finally, for when we need edge agreement in paths, note that $h(T)=q$ if $T$ is a path of length $2^{q}$ for any $q\geq 0$ .

An Alternative Way.

A recent work has reduced edge agreement in a finite tree $T=(V,E)$ to two instances of edge agreement in paths of length $\mathcal{O}(|V|)$ [19]. If one uses this reduction with our $\mathsf{TC}$ protocol serving as the path edge agreement protocol, then edge agreement in a finite tree $T=(V,E)$ costs $\mathcal{O}(\log|V|)$ rounds, $\mathcal{O}(n^{2}\log|V|)$ messages and $\mathcal{O}(n^{2}\log|V|\log\log|V|)$ bits of communication. The drawback of using the reduction here is that it can cost $\Theta(\log|V|)$ rounds even if $h(T)=o(\log|V|)$ . For example, the spider tree $T_{k,\mathcal{M}}$ for multivalued $k$ -graded consensus with the input domain $\mathcal{M}$ (the tree defined in Figure 1’s caption) has $|\mathcal{M}|k+1$ vertices, which means that the reduction allows edge agreement in $T_{k,\mathcal{M}}$ in $\Theta(\log|\mathcal{M}|+\log k)$ rounds, while $\mathsf{TC}(T_{k,\mathcal{M}})$ only takes $\mathcal{O}(\log k)$ rounds because $h(T_{k,\mathcal{M}})=\mathcal{O}(\log k)$ .

5 Edge Agreement in Infinite Paths

In this section, we achieve edge agreement in the infinite paths $\mathbb{N}$ and $\mathbb{Z}$ . First, we achieve edge agreement in $\mathbb{N}$ with a protocol based on exponential search where we again use $\mathsf{GC}_{2}$ to repeatedly shrink the agreement domain. Then, we build upon this protocol so that the parties need roughly half as many rounds to reach edge agreement when they have very large inputs. Finally, we upgrade edge agreement in $\mathbb{N}$ to edge agreement $\mathbb{Z}$ with one initial $\mathsf{GC}_{2}$ iteration.

5.1 Edge Agreement in $\mathbb{N}$

We begin with a sequence of protocols $\mathsf{Exp}_{0},\mathsf{Exp}_{1},\dots$ , with each protocol $\mathsf{Exp}_{j}$ allowing the parties to reach edge agreement in the infinite path $(2^{j}-1,\dots)$ . In $\mathsf{Exp}_{j}$ , we use $\mathsf{GC}_{2}$ to reduce edge agreement in $(2^{j}-1,\dots)$ to edge agreement in either the left path $(2^{j}-1,\dots,2^{j+1}-1)$ , which the parties can reach via $\mathsf{TC}$ , or the right path $(2^{j+1}-1,\dots)$ , which the parties can recursively²²2Note that one could recast the recursive protocol sequence $\mathsf{Exp}_{0},\mathsf{Exp}_{1},\dots$ as a single iterative protocol. reach via $\mathsf{Exp}_{j+1}$ . At some point, this recursion ends: When the parties run $\mathsf{Exp}_{0}$ with inputs in $\{0,\dots,M\}$ for some $M\geq 0$ , there is eventually some $q\leq\lfloor\log_{2}(\max(M,1))\rfloor$ such that in $\mathsf{Exp}_{q}$ (which recursively appears in $\mathsf{Exp}_{0}$ ) the parties do not prefer the right path $(2^{q+1}-1,\dots)$ as they have inputs below $2^{q+1}$ , and consequently they reach edge agreement in the finite left path $(2^{q}-1,\dots,2^{q+1}-1)$ .

Figure 3: A depiction of how each party behaves in

\mathsf{Exp}_{j}

, depending on the party’s

\mathsf{\mathsf{GC}_{2}}

output. The crucial observation is that the parties always obtain

\mathsf{GC}_{2}

outputs that are adjacent in the figure. Note that a party can output

2^{j+1}-1

by receiving

t+1

CENTER messages before it outputs from

\mathsf{GC}_{2}

.

Theorem 3.

For any positive integer $q$ and any $0\leq j<q$ , suppose the honest parties run $\mathsf{Exp}_{j}$ with inputs in $\{2^{j}-1,\dots,2^{q}-1\}$ . Then, they reach edge agreement in the path $\mathbb{N}$ based on their inputs in at most $6(j+1)$ rounds if they have the common input $2^{j}-1$ and in at most $12q-6j-5$ rounds otherwise.

We prove Theorem 3 in the appendix, with a proof similar to the one of Theorem 2. Note that the value $q$ in the theorem is not something that the parties need to know to run $\mathsf{Exp}_{j}$ .

Complexity of $\mathsf{Exp}_{0}$ .

Consider an $\mathsf{Exp}_{0}$ execution with the maximum honest input $M$ . Let $q=\lfloor\log_{2}(\max(M,1))\rfloor+1$ , i.e., let $q$ be the least positive integer such that every honest input is below $2^{q}$ . There is a minimum $k\in\{0,\dots,q-1\}$ such that in $\mathsf{Exp}_{k}$ (recursively a subprotocol of $\mathsf{Exp}_{0}$ if $k>0$ ), the parties do not set $\mathsf{side}=\texttt{RIGHT}$ and therefore do not run $\mathsf{Exp}_{k+1}$ . So, the $\mathsf{Exp}_{0}$ execution consists of the $\mathsf{GC}_{2}$ instances and the LEFT/CENTER/RIGHT multicasts of $\mathsf{Exp}_{0},\mathsf{Exp}_{1},\dots,\mathsf{Exp}_{k}$ , plus the $\mathsf{TC}((2^{k}-1,\dots,2^{k+1}-1))$ instance of $\mathsf{Exp}_{k}$ . These total up to $\mathcal{O}(n^{2}q)=\mathcal{O}(n^{2}\log M)$ messages, each of size $\mathcal{O}(\log q)=\mathcal{O}(\log\log M)$ due to the message tags since for all $j\geq 0$ one can assign $\mathcal{O}(\log j)$ -bit tags to $\mathsf{Exp}_{j}$ and to its $\mathsf{GC}_{2}$ and $\mathsf{TC}$ subprotocols. Meanwhile, the round complexity is at most $12q-5=12\log_{2}M+\mathcal{O}(1)$ , by Theorem 3.

5.2 Nearly Halving the Round Complexity

The protocol $\mathsf{Exp}_{0}$ is based on exponential search, which is a search algorithm to find a target value $x\in\mathbb{N}$ with approximately $2\log_{2}x$ checks for different choices of $v$ whether $v\leq x$ or not. Each such check roughly corresponds to a 6-round $\mathsf{GC}_{2}$ instance in $\mathsf{Exp}_{0}$ , and thus $\mathsf{Exp}_{0}$ takes $12\log_{2}M+\mathcal{O}(1)$ rounds by the simple fact that $2\cdot 6=12$ . However, it is possible to almost halve the number of checks. The strategy for this, from [6], is to accelerate exponential search by using it to find $q=\lfloor\log_{2}(x+1)\rfloor$ instead of $x$ , and then, knowing that $2^{q}-1\leq x\leq 2^{q+1}-2$ , to run binary search with the lower and upper bounds $2^{q}-1$ and $2^{q+1}-2$ to find $x$ .

Below, we use an analogous strategy in our protocol $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ for edge agreement in $\mathbb{N}$ , where we let $\mathsf{Agr}_{\mathsf{N}}$ be any protocol for edge agreement in $\mathbb{N}$ , and accelerate $\mathsf{Agr}_{\mathsf{N}}$ by using it in a two-stage manner. In $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ , the parties roughly speaking use $\mathsf{Agr}_{\mathsf{N}}$ to agree on some $k$ such that the path $(2^{k}-1,\dots,2^{k+1}-1)$ intersects the convex hull of the honest inputs, with each party $P_{i}$ with the input $v_{i}$ wanting $k$ to be $\lfloor\log_{2}(v_{i}+1)\rfloor$ . Then, each party with an input outside this path adopts a new safe value in the path (the path endpoint closest to its value), and finally the parties run $\mathsf{TC}$ to reach edge agreement in the path. Naturally, we face the issue that $\mathsf{Agr}_{\mathsf{N}}$ does not guarantee agreement on a single $k$ , which means that the parties might output different (though adjacent) $k$ values from it and therefore behave differently after outputting from $\mathsf{Agr}_{\mathsf{N}}$ . Luckily, by making each party $P_{i}$ let its $\mathsf{Agr}_{\mathsf{N}}$ input be what it wants $5k$ to be ( $5\lfloor\log_{2}(v_{i}+1)\rfloor$ ) rather than what it wants $k$ to be, we can ensure that the discrepancy between how each party behaves after outputting from $\mathsf{Agr}_{\mathsf{N}}$ is sufficiently small.

Theorem 4.

Suppose $\mathsf{Agr}_{\mathsf{N}}$ is a live protocol for edge agreement in $\mathbb{N}$ which for some function $f$ takes at most $f(M)$ rounds when the honest parties run it with inputs in $\{0,\dots,M\}$ . Then, $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ is a live protocol for edge agreement in $\mathbb{N}$ that takes at most $f(5\lfloor\log_{2}(M+1)\rfloor)+\linebreak 6\lfloor\log_{2}(M+1)\rfloor+1$ rounds when the honest parties run it with inputs in $\{0,\dots,M\}$ .

We prove Theorem 4 in the appendix, with a proof similar to the one of Theorem 2. Though $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ does not explicitly use graded consensus, it depends on the same core idea as $\mathsf{TC}$ and $\mathsf{Exp}$ : The parties reach graded consensus on how to behave, and thus they behave well together. We do not need an actual graded consensus protocol in $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ to implement this idea as the “grades” in $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ are provided directly by $\mathsf{Agr}_{\mathsf{N}}$ , in the form of the $r_{i}$ value which a party $P_{i}$ obtains as the remainder when it divides its $\mathsf{Agr}_{\mathsf{N}}$ output by $5$ .

With $\mathsf{2\textsf{-}Step}$ one can obtain a sequence of protocols $\Pi_{1}=\mathsf{Exp}_{0},\Pi_{2}=\mathsf{2\textsf{-}Step}(\Pi_{1}),\Pi_{3}=% \mathsf{2\textsf{-}Step}(\Pi_{2}),\dots$ for edge agreement in $\mathbb{N}$ , with each protocol $\Pi_{k}$ corresponding to the algorithm $B_{k}$ in [6]. Letting $f_{k}(M)$ be $\Pi_{k}$ ’s round complexity depending on the maximum honest input $M$ , we have $f_{1}(M)=12\log_{2}M+\mathcal{O}(1)$ and $f_{k+1}(M)=f_{k}(5\lfloor\log_{2}(M+1)\rfloor)+6\lfloor\log_{2}(M+1)\rfloor+1$ for all $k\geq 1$ . One can show by induction that $f_{k}(M)=6(L^{(k)}(M)+\sum_{j=1}^{k}L^{(j)}(M))+\mathcal{O}(k)$ for all $k\geq 1$ , where $L^{(1)}(v)=\lfloor\log_{2}(v+1)\rfloor$ and $L^{(k)}(v)=L(L^{(k-1)}(v))$ for all $k\geq 2$ .

The protocol $\Pi_{2}=\mathsf{2\textsf{-}Step}(\mathsf{Exp}_{0})$ above notably takes $\frac{1}{2}+\mathcal{O}(\frac{\log\log M}{\log M})=\frac{1}{2}+o(1)$ times as many rounds as $\Pi_{1}=\mathsf{Exp}_{0}$ , and only $1+o(1)$ times as many rounds as the protocols $\Pi_{3},\Pi_{4},\dots$ beyond it. Therefore, in the rest of the paper we use $\mathsf{2\textsf{-}Step}(\mathsf{Exp}_{0})$ for edge agreement in $\mathbb{N}$ .

Complexity of $\mathsf{2\textsf{-}Step}(\mathsf{Exp}_{0})$ .

Consider a $\mathsf{2\textsf{-}Step}(\mathsf{Exp}_{0})$ execution with the maximum honest input $M$ , and let $q=\lfloor\log_{2}(M+1)\rfloor$ . The initial $\mathsf{Exp}_{0}$ in $\mathsf{2\textsf{-}Step}(\mathsf{Exp}_{0})$ costs $12\log_{2}q+\mathcal{O}(1)$ rounds, $\mathcal{O}(n^{2}\log q)$ messages and $\mathcal{O}(n^{2}\log q\log\log q)$ bits of communication in total. Then, in $\mathsf{2\textsf{-}Step}(\mathsf{Exp}_{0})$ ’s remaining $6q+1$ rounds, each party $P_{i}$ runs an instance of $\mathsf{TC}$ . Due to $\mathsf{GC}_{2}$ and thus $\mathsf{TC}$ being fully symmetric protocols with balanced communication, each party $P_{i}$ (with an $\mathsf{Exp}_{0}$ output $z_{i}$ that is upper bounded by $5q$ ) sends $\mathcal{O}(nz_{i})=\mathcal{O}(nq)$ messages and $\mathcal{O}(nz_{i}\log z_{i})=\mathcal{O}(nq\log q)$ bits to the others in $\mathsf{TC}$ . So, we conclude that $\mathsf{2\textsf{-}Step}(\mathsf{Exp}_{0})$ takes $12\log_{2}q+6q+\mathcal{O}(1)=6\log_{2}M+12\log_{2}\log_{2}M+\mathcal{O}(1)$ rounds, with $\mathcal{O}(n^{2}q)=\mathcal{O}(n^{2}\log M)$ messages and $\mathcal{O}(n^{2}q\log q)=\mathcal{O}(n^{2}\log M\log\log M)$ bits of communication in total.

5.3 Edge Agreement in $\mathbb{Z}$

As before, let $\mathsf{Agr}_{\mathsf{N}}$ be a protocol for edge agreement in $\mathbb{N}$ . Observe that the parties can reach edge agreement in $(\dots,-1,0)$ by mirroring their inputs (multiplying them by $-1$ ), running $\mathsf{Agr}_{\mathsf{N}}$ with their mirrored inputs, and mirroring their $\mathsf{Agr}_{\mathsf{N}}$ outputs. This allows the protocol $\mathsf{Agr}_{\mathsf{Z}}(\mathsf{Agr}_{\mathsf{N}})$ above for edge agreement in $\mathbb{Z}$ , where the parties run $\mathsf{GC}_{2}$ with the input $-1$ if they have negative $\mathsf{Agr}_{\mathsf{Z}}$ inputs and the input $1$ otherwise, and afterwards use their $\mathsf{GC}_{2}$ outputs to determine how they should run $\mathsf{Agr}_{\mathsf{N}}$ . Note that [23] upgrades agreement in $\mathbb{N}$ to agreement in $\mathbb{Z}$ similarly, though with byzantine agreement instead of 2-graded consensus.

Theorem 5.

If $\mathsf{Agr}_{\mathsf{N}}$ is a live protocol for edge agreement in $\mathbb{N}$ , then $\mathsf{Agr}_{\mathsf{Z}}(\mathsf{Agr}_{\mathsf{N}})$ is a live protocol for edge agreement in $\mathbb{Z}$ .

We prove Theorem 5 in the appendix, with a proof similar to the one of Theorem 2.

Complexity.

When the honest parties run $\mathsf{Agr}_{\mathsf{Z}}(\mathsf{Agr}_{\mathsf{N}})$ with inputs in $\{-M,\dots,M\}$ for some $M\geq 0$ , they run $\mathsf{GC}_{2}$ , and then run $\mathsf{Agr}_{\mathsf{N}}$ with inputs upper bounded by $M$ . So, the $\mathsf{Agr}_{\mathsf{Z}}$ outer shell adds an overhead of $6$ rounds, $\mathcal{O}(n^{2})$ messages and $\mathcal{O}(n^{2})$ bits of communication to $\mathsf{Agr}_{\mathsf{N}}$ . If $\mathsf{Agr}_{\mathsf{N}}=\mathsf{2\textsf{-}Step}(\mathsf{Exp}_{0})$ , then $\mathsf{Agr}_{\mathsf{Z}}(\mathsf{Agr}_{\mathsf{N}})$ ’s complexity is $6\log_{2}M+\mathcal{O}(\log\log M)$ rounds, $\mathcal{O}(n^{2}\log M)$ messages and $\mathcal{O}(n^{2}\log M\log\log M)$ bits of communication.

6 Termination

Our edge agreement and graded consensus protocols do not terminate. They require every honest party to run forever, and lose liveness if any honest party ever halts. Fortunately, there is a simple 3-round quadratic-complexity protocol $\mathsf{Term}$ which can address this shortcoming. We present it in the appendix. It is the same termination procedure as the one on page 18 in [28], with only cosmetic changes. It relies on the fact that edge agreement implies agreement on at most two values, i.e., implies that that for some $y$ and $y^{\prime}$ everybody outputs $y$ or $y^{\prime}$ . Note that unlike our other protocols, $\mathsf{Term}$ does not require every honest party to acquire an input.

Theorem 6.

In any $\mathsf{Term}$ execution where the maximum honest message delay is $\Delta$ and the honest parties only acquire inputs in some set $\{y,y^{\prime}\}$ , if by some time $T$ either every honest party acquires an input in $\{y,y^{\prime}\}$ or some honest party terminates $\mathsf{Term}$ , then by the time $T+3\Delta$ every honest party terminates $\mathsf{Term}$ with an output that is an honest party’s input.

We prove Theorem 6 in the appendix, with a proof similar to one of Theorem 6 in [28].

For any edge agreement protocol $\Pi$ , there is an edge agreement protocol $\mathsf{Term}\circ\Pi$ in which the parties reach edge agreement with $\Pi$ and terminate with $\mathsf{Term}$ . In it, the parties run $\Pi$ with their inputs, run $\mathsf{Term}$ by using their $\Pi$ outputs as their $\mathsf{Term}$ inputs and terminate the whole protocol upon terminating $\mathsf{Term}$ , letting their $\mathsf{Term}$ outputs be their final outputs. The composed protocol $\mathsf{Term}\circ\Pi$ inherits $\Pi$ ’s agreement and validity properties since each honest $\mathsf{Term}$ output is some honest party’s $\Pi$ output. Moreover, if $\Pi$ achieves liveness in $k$ rounds, then $\mathsf{Term}\circ\Pi$ terminates in $k+3$ rounds. This is because after $k$ rounds, either every honest has output from $\Pi$ and thus acquired a $\mathsf{Term}$ input, or some honest party has terminated $\mathsf{Term}$ . Either way, the honest parties all terminate $\mathsf{Term}$ within $k+3$ rounds of every honest party acquiring a $\Pi$ input. Note that some honest parties might terminate $\mathsf{Term}$ before $k$ rounds have passed and stop running $\Pi$ before everybody outputs from $\Pi$ . This might cause $\Pi$ to lose its liveness, meaning that some honest parties might never output from $\Pi$ and thus never acquire $\mathsf{Term}$ inputs. This is not an issue because if some honest party terminates $\mathsf{Term}$ , then every honest party terminates $\mathsf{Term}$ , even if not every honest party acquires a $\mathsf{Term}$ input.

In $\mathsf{Term}$ , each honest party multicasts one constant-size READY message and at most one $\langle{\texttt{ECHO}},{v}\rangle$ message for each honest input $v$ . So, the overhead of terminating an edge agreement protocol $\Pi$ with $\mathsf{Term}$ is $3$ rounds and $\mathcal{O}(n^{2})$ messages which each carry honest $\Pi$ outputs.

Termination for edge agreement in $\mathbb{Z}$ .

If the parties terminate with $\mathsf{Term}$ after reaching edge agreement in $\mathbb{Z}$ with inputs of magnitude at most $M$ , then each honest $\mathsf{Term}$ input is an integer in $\{-M,\dots,M\}$ , with an $\mathcal{O}(\log M)$ -bit representation. So, for any live protocol $\mathsf{Agr}_{\mathsf{Z}}$ for edge agreement in $\mathbb{Z}$ , $\mathsf{Term}\circ\mathsf{Agr}_{\mathsf{Z}}$ is a terminating protocol for edge agreement in $\mathbb{Z}$ which costs $3$ more rounds, $\mathcal{O}(n^{2})$ more messages and $\mathcal{O}(n^{2}\log M)$ more bits of communication than $\mathsf{Agr}_{\mathsf{Z}}$ .

Termination for edge agreement in trees.

If the parties run $\mathsf{Term}$ to terminate after they reach edge agreement in a tree $T=(V,E)$ , then each honest $\mathsf{Term}$ input is a vertex in $V$ , with an $\mathcal{O}(\log|V|)$ -bit representation. So, $\mathsf{Term}\circ\mathsf{TC}(T)$ is a terminating version of $\mathsf{TC}(T)$ that costs $3$ rounds, $\mathcal{O}(n^{2})$ messages and $\mathcal{O}(n^{2}\log|V|)$ bits of communication more than $\mathsf{TC}(T)$ . Note that $\mathsf{Term}$ here does not asymptotically cost more communication than $\mathsf{TC}(T)$ because we have $h(T)=\Omega(\log_{\Delta}|V|)$ , where $\Delta$ is $T$ ’s maximum degree. To see why, let $h_{\Delta}(k)$ for any $k\geq 1$ be the minimum value $h(T)$ can have for any tree $T$ of maximum degree at most $\Delta\geq 2$ with at least $k$ vertices, and observe that $h_{\Delta}(k)\geq 1+h_{\Delta}(\lceil\frac{k-1}{\Delta}\rceil)$ for all $k\geq 2$ as removing a centroid of degree at most $\Delta$ from a tree with at least $k\geq 2$ vertices creates a forest whose largest component has at least $\lceil\frac{k-1}{\Delta}\rceil$ vertices. By induction, this implies $h_{\Delta}(\Delta^{k})\geq k$ for all $k\geq 0$ .

7 Extension to Real Numbers

Termination is harder for approximate agreement in $\mathbb{R}$ . As approximate agreement in $\mathbb{R}$ does not entail agreement on two values, $\mathsf{Term}$ alone cannot directly provide termination. So, to achieve approximate agreement in $\mathbb{R}$ with termination, we reduce it to edge agreement in $\mathbb{Z}$ .

Theorem 7.

For all $\varepsilon>0$ , $\varepsilon$ -agreement in $\mathbb{R}$ with the maximum honest input magnitude $M$ can be reduced to edge agreement in $\mathbb{Z}$ with the maximum honest input magnitude $\lceil\frac{2M}{\varepsilon}-\frac{1}{2}\rceil$ .

Proof.

We reduce $2$ -agreement in $\mathbb{R}$ with the maximum honest input magnitude $M$ to edge agreement in $\mathbb{Z}$ with the maximum honest input magnitude $\lceil M-\frac{1}{2}\rceil$ . This reduction implies the theorem since the parties can reach $\varepsilon$ -agreement in $\mathbb{R}$ by multiplying their inputs by $\frac{2}{\varepsilon}$ , reaching $2$ -agreement, and dividing their outputs by $\frac{2}{\varepsilon}$ .

Each party $P_{i}$ rounds its $2$ -agreement input $v_{i}$ to the nearest integer $v_{i}^{\prime}$ , rounding towards $0$ in the case of ties. Then, the parties reach edge agreement in $\mathbb{Z}$ with their rounded integers of magnitude at most $\lceil M-\frac{1}{2}\rceil$ , and each party $P_{i}$ obtains some edge agreement output $y_{i}^{\prime}$ . For all honest parties $P_{i}$ and $P_{j}$ it holds that $|y_{i}^{\prime}-y_{j}^{\prime}|\leq 1$ and that $v_{a}^{\prime}\leq y_{i}^{\prime}\leq v_{b}^{\prime}$ , where $a$ and $b$ are respectively the indices of the honest parties with the minimum and maximum edge agreement inputs. Observe that this implies $v_{a}-\frac{1}{2}\leq v_{a}^{\prime}\leq y_{i}^{\prime}\leq v_{b}^{\prime}\leq v% _{b}+\frac{1}{2}$ for all honest $P_{i}$ .

Afterwards, each party $P_{i}$ uses its 2-agreement input $v_{i}$ to convert $y_{i}^{\prime}$ into its $2$ -agreement output $y_{i}$ by letting $y_{i}=\min(y_{i}^{\prime}+\frac{1}{2},v_{i})$ if $y_{i}^{\prime}\leq v_{i}$ , and $y_{i}=\max(y_{i}^{\prime}-\frac{1}{2},v_{i})$ otherwise. That is, $P_{i}$ obtains $y_{i}$ by moving from $y_{i}^{\prime}$ towards its input $v_{i}$ by a distance of at most $\frac{1}{2}$ . For all honest $P_{i}$ and $P_{j}$ it holds that $\min(v_{a},v_{i})\leq y_{i}\leq\max(v_{b},v_{i})$ , which implies validity, and that $|y_{i}-y_{j}|\leq|y_{i}-y_{i}^{\prime}|+|y_{i}^{\prime}-y_{j}^{\prime}|+|y_{j}% ^{\prime}-y_{j}|\leq\frac{1}{2}+1+\frac{1}{2}=2$ , which implies $2$ -agreement. $\hfill\blacktriangleleft$

As we can achieve edge agreement in $\mathbb{Z}$ in $6\log_{2}M+\mathcal{O}(\log\log M)$ rounds with $\mathcal{O}(n^{2}\log M)$ messages and $\mathcal{O}(n^{2}\log M\log\log M)$ bits of communication, the reduction enables $\varepsilon$ -agreement in $\mathbb{R}$ in $6\log_{2}\frac{M}{\varepsilon}+\mathcal{O}(\log\log\frac{M}{\varepsilon})$ rounds with $\mathcal{O}(n^{2}\log\frac{M}{\varepsilon})$ messages and $\mathcal{O}(n^{2}\log\frac{M}{\varepsilon}\log\log\frac{M}{\varepsilon})$ bits of communication. Note that $M$ here is (as always in this paper) not a parameter which must be known in advance, but a dynamic value that depends on the honest parties’ inputs.

Our reduction allows the parties to reach $\varepsilon$ -agreement in $\mathbb{R}$ by only sending each other discrete messages. So, it allows approximate agreement without any value rounding errors. In contrast, protocols where the parties send values in $\mathbb{R}$ [14, 1, 21, 5] must in order to avoid rounding errors assume that the inputs in $\mathbb{R}$ fit $\ell$ -bit strings, with $\ell$ affecting complexity.

Future Work.

It remains open to design a protocol for $\varepsilon$ -agreement in $\mathbb{R}$ that tolerates $t<\frac{n}{3}$ faults with quadratic communication in $\mathcal{O}(\log\frac{S}{\varepsilon})$ rounds, where $S$ is the honest input spread. Our protocol takes $\mathcal{O}(\log\frac{M}{\varepsilon})$ rounds, where possibly $M\gg S$ , while [1] takes $\mathcal{O}(\log\frac{S}{\varepsilon})$ rounds but requires cubic communication. In fact, this task is open even for the synchronous setting. The classical synchronous protocol in [14] takes as many rounds as the adversary wants since its complexity scales with the the spread of all inputs, including byzantine ones. Solving this issue remains open, especially in the asynchronous setting where a new approach seems necessary.

References

[1] Ittai Abraham, Yonatan Amit, and Danny Dolev. Optimal resilience asynchronous approximate agreement. In Proceedings of the 8th International Conference on Principles of Distributed Systems, OPODIS ’04, pages 229–239, Berlin, Heidelberg, 2004. Springer-Verlag. doi:10.1007/11516798_17.
[2] Ittai Abraham, T-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication complexity of byzantine agreement, revisited. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19, pages 317–326, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3293611.3331629.
[3] Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang. Balanced byzantine reliable broadcast with near-optimal communication and improved computation. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC ’22, pages 399–417, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3519270.3538475.
[4] Hagit Attiya and Jennifer L. Welch. Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023), volume 286 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:23, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.OPODIS.2023.6.
[5] Akhil Bandarupalli, Adithya Bhat, Saurabh Bagchi, Aniket Kate, Chen-Da Liu-Zhang, and Michael K. Reiter. Delphi: Efficient Asynchronous Approximate Agreement for Distributed Oracles. In 2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 456–469, Los Alamitos, CA, USA, June 2024. IEEE Computer Society. doi:10.1109/DSN58291.2024.00051.
[6] Jon Louis Bentley and Andrew Chi-Chih Yao. An almost optimal algorithm for unbounded searching. Information Processing Letters, 5(3):82–87, 1976. doi:10.1016/0020-0190(76)90071-5.
[7] Erica Blum, Jonathan Katz, and Julian Loss. Synchronous consensus with optimal asynchronous fallback guarantees. In Theory of Cryptography — TCC 2019, Cham, Switzerland, 2019. Springer International Publishing. doi:10.1007/978-3-030-36030-6_6.
[8] Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2), 1987. doi:10.1016/0890-5401(87)90054-X.
[9] Jing Chen and Silvio Micali. Algorand: A secure and efficient distributed ledger. Theor. Comput. Sci., 777(C):155–183, July 2019. doi:10.1016/j.tcs.2019.02.001.
[10] B. A. Coan. A compiler that increases the fault tolerance of asynchronous protocols. IEEE Trans. Comput., 37(12):1541–1553, December 1988. doi:10.1109/12.9732.
[11] Andrei Constantinescu, Diana Ghinea, Roger Wattenhofer, and Floris Westermann. Convex Consensus with Asynchronous Fallback. In 38th International Symposium on Distributed Computing (DISC 2024), volume 319 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:23, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2024.15.
[12] Giovanni Deligios and Mose Mizrahi Erbes. Closing the efficiency gap between synchronous and network-agnostic consensus. In Advances in Cryptology – EUROCRYPT 2024, pages 432–461, Cham, 2024. Springer Nature Switzerland. doi:10.1007/978-3-031-58740-5_15.
[13] D. Dolev and H. R. Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656–666, 1983. doi:10.1137/0212045.
[14] Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. J. ACM, 33(3):499–516, May 1986. doi:10.1145/5925.5931.
[15] Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for byzantine agreement. J. ACM, 32(1):191–204, January 1985. doi:10.1145/2455.214112.
[16] Maya Dotan, Gilad Stern, and Aviv Zohar. Validated byzantine asynchronous multidimensional approximate agreement, 2022. doi:10.48550/arXiv.2211.02126.
[17] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382, April 1985. doi:10.1145/3149.214121.
[18] Matthias Fitzi, Chen-Da Liu-Zhang, and Julian Loss. A new way to achieve round-efficient byzantine agreement. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC ’21, pages 355–362, New York, NY, USA, 2021. Association for Computing Machinery. doi:10.1145/3465084.3467907.
[19] Marc Fuchs, Diana Ghinea, and Zahra Parsaeian. Brief announcement: Towards round-optimal approximate agreement on trees. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 54–57, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3732772.3733555.
[20] Diana Ghinea, Vipul Goyal, and Chen-Da Liu-Zhang. Round-optimal byzantine agreement. In Advances in Cryptology – EUROCRYPT 2022, pages 96–119, Cham, 2022. Springer International Publishing. doi:10.1007/978-3-031-06944-4_4.
[21] Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Optimal synchronous approximate agreement with asynchronous fallback. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC ’22, pages 70–80, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3519270.3538442.
[22] Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Multidimensional approximate agreement with asynchronous fallback. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’23, pages 141–151, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3558481.3591105.
[23] Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Communication-optimal convex agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 39–49, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3732772.3733551.
[24] Camille Jordan. Sur les assemblages de lignes. Journal für die reine und angewandte Mathematik, 70:185–190, 1869. URL: http://eudml.org/doc/148084.
[25] Simon Holmgaard Kamp. A new way to achieve round-efficient asynchronous byzantine agreement. Cryptology ePrint Archive, Paper 2025/143, 2025. URL: https://eprint.iacr.org/2025/143.
[26] Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya, and Vijay K. Garg. Multidimensional agreement in byzantine systems. Distrib. Comput., 28(6):423–441, December 2015. doi:10.1007/s00446-014-0240-5.
[27] Mose Mizrahi Erbes and Roger Wattenhofer. Brief Announcement: Asynchronous Approximate Agreement with Quadratic Communication. In Dariusz R. Kowalski, editor, 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61:1–61:7, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2025.61.
[28] Mose Mizrahi Erbes and Roger Wattenhofer. Quit-Resistant Reliable Broadcast and Efficient Terminating Gather. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024), volume 324 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:22, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.OPODIS.2024.15.
[29] Thomas Nowak and Joel Rybicki. Byzantine Approximate Agreement on Graphs. In 33rd International Symposium on Distributed Computing (DISC 2019), volume 146 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2019.29.
[30] A simple introduction to centroid decomposition. A Simple Blog, 2020. Accessed: 2025-08-15. URL: https://robert1003.github.io/2020/01/16/centroid-decomposition.html.

Appendix A Graded Consensus Protocols

In this section, we design a family of $2^{k}$ -graded consensus protocols $\mathsf{GC}_{2^{0}},\mathsf{GC}_{2^{1}},\mathsf{GC}_{2^{2}},\dots$ that support inputs in $\{0,1\}^{\ell}$ for any public length parameter $\ell\geq 1$ . The complexity of each protocol $\mathsf{GC}_{2^{k}}$ is $3k+3$ rounds, $\mathcal{O}(kn^{2})$ messages and $\mathcal{O}(kn^{2}(\ell+\log k))$ bits of communication. To obtain these protocols we begin with the 3-round $\mathsf{GC}_{1}$ , and then for all $k\geq 1$ obtain $\mathsf{GC}_{2^{k}}$ by grade-doubling $\mathsf{GC}_{2^{k-1}}$ in 3 rounds. While we only use $\mathsf{GC}_{2}$ in this paper, note that grades above 2 can also be useful, as $2^{k}$ -graded consensus forms the “expand” part of the “expand-and-extract” paradigm of achieving byzantine agreement with an $\mathcal{O}(2^{-k})$ error probability [18].

As $2^{k}$ -graded consensus is a special case of edge agreement with the centroid decomposition height $k+1$ (see Figure 1), our edge agreement protocol $\mathsf{TC}$ is also a $2^{k}$ -graded consensus protocol, but one that takes up to $6k+7$ rounds. The more restricted definition of $2^{k}$ -graded consensus allow us to achieve it in $3k+3$ rounds instead. This is the round complexity of the binary $2^{k}$ -graded consensus protocol in [5], and it is for all $k\geq 0$ lower than the round complexity of any previous multivalued $2^{k}$ -graded consensus protocol which we know of that tolerates $t<\frac{n}{3}$ faults with perfect security. Note that $2^{k}$ -graded consensus can be achieved in less rounds than $3k+3$ if $t<\frac{n}{5}$ ( $k+1$ rounds [14, 4]) or if the parties can use a cryptographic setup ( $k+2$ rounds, [25]). If in our edge agreement protocols we replaced $\mathsf{GC}_{2}$ with a faster $r$ -round $2$ -graded consensus protocol, then our edge agreement protocols would become $\frac{6}{r}$ times faster, excluding some constant round complexity terms that would not change.

A.1 1-Graded Consensus

Below is our live 3-round multivalued 1-graded consensus protocol $\mathsf{GC}_{1}$ .

This protocol is based on the 4-round protocol $\mathsf{AWC}$ in [12]. Our addition is the list of sets $V_{i}^{1},\dots,V_{i}^{\ell}$ , which $\mathsf{AWC}$ does not have. While according to $\mathsf{AWC}$ a party $P_{i}$ would output $(\bot,0)$ upon observing that $W_{i}^{k}=\{0,1\}$ for some $k$ , in $\mathsf{GC}_{1}$ a party $P_{i}$ outputs $(\bot,0)$ upon observing that $V_{i}^{k}=\{0,1\}$ . As the parties fill their $V$ sets more readily than their $W$ sets (due to Line 7 having a weaker condition than Line 11), the $V$ sets let us shave off one round.

Theorem 8.

$\mathsf{GC}_{1}$ is a secure $3$ -round $1$ -graded consensus protocol with liveness.

Proof.

The simplest property is intrusion tolerance. It follows from the fact that if an honest party outputs $(v,1)$ for any $v$ , then $v$ is the party’s input, which makes it an honest input.

Agreement is also simple. Suppose there are two honest parties $P$ and $P^{\prime}$ who respectively output $(v,1)$ and $(v^{\prime},1)$ . Then, $P$ has received $n-t$ proposals on $v$ , while $P^{\prime}$ has received $n-t$ proposals on $v^{\prime}$ . Hence, there are $n-2t\geq t+1$ parties, or at least one honest party, who have sent $P$ a proposal on $v$ and $P^{\prime}$ a proposal on $v^{\prime}$ . This implies that $v=v^{\prime}$ because an honest party can only propose one value. The reason why this is true is that an honest party $P_{i}$ only proposes a value when it adds a bit to one of its $W$ sets $W_{i}^{1},\dots,W_{i}^{\ell}$ and after doing so observes that $|W_{i}^{1}|=\dots=|W_{i}^{\ell}|=1$ , which can happen only once.

For validity, suppose the honest parties have a common input $v^{*}=b_{1}^{*}\|\dots\|b_{\ell}^{*}\in\{0,1\}^{\ell}$ . In this case, they echo $v^{*}$ (multicast $\langle{\texttt{ECHO}},{v^{*}}\rangle$ ), and they do not echo $\bot$ since they do not receive $t+1$ echoes on values other than $v^{*}$ . For all $k\in\{1,\dots,\ell\}$ , since no honest party echoes $\bot$ or a string with the $k^{\text{th}}$ bit $1-b_{k}^{*}$ , the bit $b_{k}^{*}$ is the only bit that any honest party $P_{i}$ can add to $V_{i}^{k}$ or $W_{i}^{k}$ . Consequently, an honest party can neither output $(\bot,0)$ on Line 10 nor propose anything other than $v^{*}$ . This means that an honest party can only output after receiving $n-t$ proposals on $v^{*}$ , which leads to the party outputting $v^{*}$ since it has the input $v^{*}$ .

Finally, for liveness in 3 rounds, suppose that by some time $T$ every honest party acquires its input and thus echoes it. We show via case analysis that every honest party outputs by the time $T+3\Delta$ , where $\Delta$ is the maximum honest message delay that the adversary causes.

1.

The easier case is if there is no input that $t+1$ honest parties have. Then, by the time $T+\Delta$ , every honest party receives $n-2t\geq t+1$ echo messages on inputs that are not its own, and therefore becomes able to output $\bot$ .
2.

Suppose instead that some $v^{*}=b_{1}^{*}\|\dots\|b_{\ell}^{*}\in\{0,1\}^{\ell}$ is the input of $t+1$ honest parties. By the time $T+\Delta$ , all the honest parties with inputs other than $v^{*}$ receive $t+1$ echoes on $v^{*}$ and thus echo $\bot$ . Then, by the time $T+2\Delta$ , for each $k\in\{1,\dots,\ell\}$ each honest party $P_{i}$ receives $n-t\geq 2t+1$ echoes that are on $\bot$ or $v^{*}$ (which has the $k^{\text{th}}$ bit $b_{i}^{*}$ ), and thus adds $b_{i}^{*}$ to $W_{i}^{k}$ . So, by the time $T+2\Delta$ , either every honest party $P_{i}$ observes that $W_{i}^{k}=\{b_{k}^{*}\}$ for all $k$ , or some honest party $P_{i}$ obtains $W_{i}^{k}=\{0,1\}$ . In the former case, the honest parties all propose $v^{*}$ , which by the time $T+3\Delta$ leads to them all receiving $n-t$ proposals on $v^{*}$ and thus becoming able to output $(v^{*},1)$ or $(\bot,0)$ . In the latter case, the honest party $P_{i}$ with $W_{i}^{k}=\{0,1\}$ has by the time $T+2\Delta$ for both bits $b\in\{0,1\}$ received echo messages on $\bot$ or on strings with the $k^{\text{th}}$ bit $b$ from $n-t$ parties ( $t+1$ or more of which are honest). Hence, by the time $T+3\Delta$ , for both bits $b\in\{0,1\}$ every honest party $P_{j}$ receives from $t+1$ honest parties echoes on $\bot$ or on strings with the $k^{\text{th}}$ bit $b$ , which means that $P_{j}$ obtains $V_{j}^{k}=\{0,1\}$ and becomes able to output $(\bot,0)$ .

$\hfill\blacktriangleleft$

Complexity.

The round complexity is $3$ , as proven above. The message complexity is $\mathcal{O}(n^{2})$ as each party multicasts at most $3$ messages (an echo on $\bot$ , an echo on its input and a proposal), and the communication complexity is $\mathcal{O}(\ell n^{2})$ bits. Note that the communication is balanced evenly between the parties: Each party sends $\mathcal{O}(n)$ messages and $\mathcal{O}(\ell n)$ bits to the others.

A.2 Grade Doubling

We achieve grade-doubling with a proposal protocol we call $\mathsf{Prop}$ . In proposal, each party $P_{i}$ acquires an input $v_{i}\in\mathcal{M}$ in an input domain $\mathcal{M}$ , and outputs a set $Y_{i}\subseteq M$ of size $1$ or $2$ . To work properly, a proposal protocol requires there to exist a set $S$ of size $2$ (which the parties might not know in advance) such that the honest parties only acquire inputs in $S$ . If there exists such a set $S$ , a proposal protocol achieves liveness with the following safety properties:

$\blacksquare$

agreement: If $Y_{i}$ and $Y_{j}$ are honest output sets, then $Y_{i}\cap Y_{j}\neq\varnothing$ .
$\blacksquare$

validity: For every honest output set $Y_{i}$ , every $y\in Y_{i}$ is an honest party’s input.

With binary inputs, proposal is equivalent to binary 1-graded consensus. Suppose the parties run a proposal protocol with inputs in $\{0,1\}$ . If they run it with a common input bit $b^{*}$ then they all output $\{b^{*}\}$ from it, and otherwise for some bit $b^{*}$ they each output $\{b^{*}\}$ or $\{0,1\}$ from it. These output guarantees are exactly those of binary 1-graded consensus when we map the proposal outputs $\{0\},\{0,1\},\{1\}$ to the 1-graded consensus outputs $(0,1),(\bot,0),(1,1)$ . However, when there are more than two possible inputs, a binary 1-graded consensus protocol cannot be used, whereas a proposal protocol still works with output guarantees comparable to those of 1-graded consensus as long as the honest parties happen to run it with at most two inputs $a$ and $b$ , even if the parties with the input $a$ do not know what $b$ is and vice versa.

Our 3-round proposal protocol $\mathsf{Prop}$ is based on the 4-round protocol $\mathsf{AProp}$ in [12], which is in turn based on the protocol $\Pi_{\mathsf{prop}}^{t_{s}}$ in [7]. Again, we shave off one round. While according to $\mathsf{AProp}$ ’s design a party $P_{i}$ would need to receive $2t+1$ echoes on a value $v$ to add $v$ to its set $V_{i}$ , below in $\mathsf{Prop}$ the party $P_{i}$ adds $v$ to $V_{i}$ after receiving $t+1$ echoes on $v$ . This change makes it easier for $P_{i}$ to add values to $V_{i}$ , obtain $|V_{i}|=2$ and output $V_{i}$ .

Note that using proposal to double grades is not a new invention. The BinAA protocol in [5] essentially uses proposal (therein called weak binary value broadcast) for this purpose.

Theorem 9.

$\mathsf{Prop}$ is a secure 3-round proposal protocol with liveness.

Proof.

Below, we assume that there exists a set $S=\{a,b\}$ such that the honest parties only acquire inputs in $S$ . Without this, the agreement and liveness properties would be lost.

If an honest party echoes a value $v$ , then $v$ must be some honest party’s input. Otherwise, the first honest party that echoes $v$ would have to have received $t+1$ echoes on $v$ , at least one being from an honest party who contradictorily echoed $v$ earlier. For any value $v$ that is not any honest party’s input, the fact that no honest party echoes $v$ means that the honest parties cannot output sets that contain $v$ (i.e., that we have validity), due to the following:

1.

An honest party $P_{i}$ cannot add $v$ to its set $V_{i}$ , as $P_{i}$ would need to receive $t+1$ echoes on $v$ to do this. Therefore, if $P_{i}$ outputs $V_{i}$ when $|V_{i}|=2$ , then $v\not\in V_{i}$ .
2.

An honest party $P_{i}$ cannot propose $v$ , as $P_{i}$ would need to receive $2t+1$ echoes on $v$ to do this. This means that an honest party $P_{j}$ cannot output $\{v\}$ , as $P_{j}$ would have to receive $n-t\geq t+1$ proposals on $v$ to do this.

As for agreement, observe that by the validity property the honest parties can only output non-empty subsets of $S=\{a,b\}$ , as their inputs are all in $S$ . So, we only need to show that if some honest parties $P$ and $P^{\prime}$ respectively output $\{v\}$ and $\{v^{\prime}\}$ for some $v,v^{\prime}\in S$ , then $v=v^{\prime}$ . Again, this follows from a traditional quorum intersection argument. If we have such parties $P$ and $P^{\prime}$ , then $P$ has received $n-t$ proposals on $v$ , while $P^{\prime}$ has received $n-t$ proposals on $v^{\prime}$ . So, there are $n-2t\geq t+1$ parties, or at least one honest party, who have sent $P$ a proposal on $v$ and $P^{\prime}$ a proposal on $v^{\prime}$ . This implies $v=v^{\prime}$ as an honest party can only propose once.

It remains to show liveness in 3 rounds. As we did for $\mathsf{GC}_{1}$ , let us suppose that by some time $T$ every honest party has acquired an input in $\{a,b\}=S$ and thus echoed it. Let us show that every honest party outputs by the time $T+3\Delta$ , where $\Delta$ is the maximum honest message delay that the adversary causes. Since there exists some $v\in S$ that is at least $\lceil\frac{n-t}{2}\rceil\geq t+1$ honest parties’ input, we know that by the time $T+\Delta$ every honest party receives $t+1$ echoes on $v$ and thus echoes $v$ even if $v$ is not its input. Then, by the time $T+2\Delta$ , every honest party receives $n-t\geq 2t+1$ echoes on $v$ . Finally, this is followed by one of the two cases below, in both of which the honest parties all output by the time $T+3\Delta$ .

1.

It could be the case that no honest party proposes any $v^{\prime}\neq v$ by the time $T+2\Delta$ . Then, by the time $T+2\Delta$ every honest party proposes $v$ after receiving $2t+1$ echoes on $v$ . Consequently, by the time $T+3\Delta$ , every honest party receives $n-t$ proposals on $v$ , which allows the party to output $v$ if it did not output earlier.
2.

It could be the case that some honest party $P_{i}$ proposes some $v^{\prime}\neq v$ by the time $T+2\Delta$ . Then, at the time $T+2\Delta$ the party $P_{i}$ must have received $2t+1$ echoes on $v^{\prime}$ , with at least $t+1$ of these echoes being from honest parties. Since both $v$ and $v^{\prime}$ get echoed by at least $t+1$ honest parties by the time $T+2\Delta$ , we conclude that by the time $T+3\Delta$ every honest party $P_{j}$ gains the ability to output $V_{j}=\{v,v^{\prime}\}=S$ after it receives $t+1$ echoes on both $v$ and $v^{\prime}$ and thus adds both $v$ and $v^{\prime}$ to $V_{j}$ .

Complexity.

The round complexity is $3$ , as proven above. The message complexity is $\mathcal{O}(n^{2})$ as each party multicasts at most $3$ messages (two echoes and one proposal), with each honest party echo/proposal carrying an honest party’s input. Again, the communication is balanced.

$\hfill\blacktriangleleft$

With $\mathsf{Prop}$ , it is simple to grade-double $\mathsf{GC}_{2^{k-1}}$ into $\mathsf{GC}_{2^{k}}$ . All we need to do is sequentially compose $\mathsf{GC}_{2^{k-1}}$ and $\mathsf{Prop}$ , and interpret $\mathsf{Prop}$ outputs as $\mathsf{GC}_{2^{k}}$ outputs.

Theorem 10.

For all $k\geq 0$ , $\mathsf{GC}_{2^{k}}$ is a secure $2^{k}$ -graded consensus protocol with liveness.

Proof.

Naturally, this theorem follows by induction on $k$ . The base case $k=0$ is the protocol $\mathsf{GC}_{1}$ , which we have already proven secure. Below, we consider $k\geq 1$ , where we obtain $\mathsf{GC}_{2^{k}}$ by sequentially composing $\mathsf{GC}_{2^{k-1}}$ and $\mathsf{Prop}$ .

The honest parties begin by running $\mathsf{GC}_{2^{k-1}}$ with their inputs. So, for some honest input $v^{*}$ and some grade $g\in\{0,\dots,2^{k-1}-1\}$ they each output either $(v^{\prime},g)$ or $(v^{*},g+1)$ from $\mathsf{GC}_{2^{k-1}}$ , where $v^{\prime}=\bot$ if $g=0$ and $v^{\prime}=v^{*}$ if $g\geq 1$ . Afterwards, they run $\mathsf{Prop}$ with inputs in $\{(v^{\prime},g),(v^{*},g+1)\}$ , and therefore either they all output $\{(v^{\prime},g)\}$ or $\{(v^{\prime},g),(v^{*},g+1)\}$ from $\mathsf{Prop}$ and thus all output $(v^{\prime},2g)$ or $(v^{*},2g+1)$ from $\mathsf{GC}_{2^{k}}$ , or they all output $\{(v^{\prime},g),(v^{*},g+1)\}$ or $\{(v^{*},g+1)\}$ from $\mathsf{Prop}$ and thus all output $(v^{*},2g+1)$ or $(v^{*},2g+2)$ from $\mathsf{GC}_{2^{k}}$ . Either way, $\mathsf{GC}_{2^{k}}$ achieves liveness, intrusion tolerance and agreement.

If the honest parties run $\mathsf{GC}_{2^{k}}$ with a common input $v^{*}$ , then they all run $\mathsf{GC}_{2^{k-1}}$ with the input $v^{*}$ , output $(v^{*},2^{k-1})$ from it, run $\mathsf{Prop}$ with the input $(v^{*},2^{k-1})$ , output $\{(v^{*},2^{k-1})\}$ from it, and finally output $(v^{*},2^{k})$ from $\mathsf{GC}_{2^{k}}$ . Hence, $\mathsf{GC}_{2^{k}}$ achieves validity as well. $\hfill\blacktriangleleft$

Complexity.

As $\mathsf{GC}_{2^{k}}$ consists of one 3-round $\mathsf{GC}_{1}$ instance followed by $k$ sequential 3-round $\mathsf{Prop}$ iterations, $\mathsf{GC}_{2^{k}}$ ’s round complexity is $3k+3$ and its message complexity is $\mathcal{O}(kn^{2})$ . When the parties run $\mathsf{GC}_{2^{k}}$ with $\ell$ -bit inputs, they run $\mathsf{GC}_{1}$ with inputs in $\{0,1\}^{\ell}$ , and so $\mathsf{GC}_{1}$ costs $\mathcal{O}(\ell n^{2})$ bits of communication. Then, for each $j\in\{1,\dots,k\}$ they run the $j^{\text{th}}$ $\mathsf{Prop}$ iteration with inputs that are $2^{j-1}$ -graded consensus outputs in $(\{0,1\}^{\ell}\times\{1,\dots,2^{j-1}\})\cup\{(\bot,0)\}$ , of size $\mathcal{O}(\ell+\log j)=\mathcal{O}(\ell+\log k)$ , and so the $j^{\text{th}}$ $\mathsf{Prop}$ iteration costs $\mathcal{O}(n^{2}(\ell+\log k))$ bits of communication. Overall, we see that $\mathsf{GC}_{2^{k}}$ ’s communication complexity is $\mathcal{O}(kn^{2}(\ell+\log k))$ bits, with the $\log k$ term here also covering the $\mathsf{Prop}$ iterations’ ID tags. Note that the communication in $\mathsf{GC}_{2^{k}}$ is balanced, as both $\mathsf{GC}_{1}$ and $\mathsf{Prop}$ have balanced communication.

Appendix B The Termination Protocol $\mathsf{Term}$

Theorem 6.

In any $\mathsf{Term}$ execution where the maximum honest message delay is $\Delta$ and the honest parties only acquire inputs in some set $\{y,y^{\prime}\}$ , if by some time $T$ either every honest party acquires an input in $\{y,y^{\prime}\}$ or some honest party terminates $\mathsf{Term}$ , then by the time $T+3\Delta$ every honest party terminates $\mathsf{Term}$ with an output that is an honest party’s input.

Proof.

Suppose an honest party $P_{i}$ outputs some $v$ from $\mathsf{Term}$ . Then, $P_{i}$ has received $t+1$ echoes on $v$ , at least one of which is honest. An honest party only echoes a value if the value is its input or it receives $t+1$ echoes on the value (at least one of which is honest), which means that the first honest party who echoed $v$ did so because its input is $v$ . So, we see that the honest parties can only output honest party inputs from $\mathsf{Term}$ .

As for termination in $3$ rounds, let $\Delta$ be the maximum honest message delay the adversary causes. We first prove a fact we will use later: If every honest party multicasts READY by some time $T$ , then every honest party terminates by the time $T+\Delta$ . To see why, suppose every honest party multicasts READY by some time $T$ . At the time $T$ , the first honest party who has multicast READY has done so because it has received $2t+1$ echoes on some $v$ , at least $t+1$ of which are honest. So, by the time $T+\Delta$ every honest party $P_{i}$ receives $t+1$ honest echoes on $v$ , which allows $P_{i}$ to set $y_{i}\leftarrow v$ if $y_{i}=\bot$ . Moreover, since every honest party multicasts READY by the time $T$ , every honest party $P_{i}$ receives $n-t\geq 2t+1$ honest READY messages by the time $T+\Delta$ , which allows $P_{i}$ to terminate $\mathsf{Term}$ by the time $T+\Delta$ with an output $y_{i}\neq\bot$ .

Now, let us show that if an honest party $P_{i}$ terminates by some time $T$ , then every honest party terminates by the the time $T+2\Delta$ . This is because if $P_{i}$ terminates by the time $T$ , it does so after receiving READY from $2t+1$ parties, at least $t+1$ of which are honest. Since at least $t+1$ honest parties multicast READY by the time $T$ , every honest party receives $t+1$ honest READY messages and therefore multicasts READY by the time $T+\Delta$ , and consequently every honest party terminates by the time $T+2\Delta$ .

Finally, suppose that by some time $T$ every honest party acquires an input. We want to show that every honest party terminates by the time $T+3\Delta$ . If some honest party terminates by the time $T+\Delta$ , then this follows from what we have proven above; so, suppose no honest party terminates by the time $T+\Delta$ . By the time $T$ , every honest party echoes its input in $\{y,y^{\prime}\}$ , and so there exists some $y^{*}\in\{y,y^{\prime}\}$ that at least $\lceil\frac{n-t}{2}\rceil\geq t+1$ honest parties echo. By the time $T+\Delta$ , every honest party receives $t+1$ echoes on $y^{*}$ before terminating, and thus echoes $y^{*}$ even if it has not acquired the input $y^{*}$ . By the time $T+2\Delta$ , every honest party receives $n-t\geq 2t+1$ echoes on $y^{*}$ , and thus multicasts READY. Finally, by the time $T+3\Delta$ , every honest party terminates $\mathsf{Term}$ . $\hfill\blacktriangleleft$

Appendix C Skipped Proofs

Theorem 3.

For any positive integer $q$ and any $0\leq j<q$ , suppose the honest parties run $\mathsf{Exp}_{j}$ with inputs in $\{2^{j}-1,\dots,2^{q}-1\}$ . Then, they reach edge agreement in the path $\mathbb{N}$ based on their inputs in at most $6(j+1)$ rounds if they have the common input $2^{j}-1$ and in at most $12q-6j-5$ rounds otherwise.

Proof.

To prove the theorem, we pick any arbitrary $q\geq 1$ , and by induction prove for each $j\in\{q-1,q-2,\dots,0\}$ (in this order) that $\mathsf{Exp}_{j}$ is a protocol for edge agreement in the path $(2^{j}-1,\dots,2^{q}-1)$ that takes at most $6(j+1)$ rounds if run with the common input $2^{j}-1$ and at most $12q-6j-5$ rounds otherwise.

Note that for any $j\geq 0$ , if no honest party obtains the grade $0$ from $\mathsf{GC}_{2}$ in $\mathsf{Exp}_{j}$ , then no honest party multicasts CENTER, and thus no honest party outputs $2^{j+1}-1$ on Line 22 upon receiving CENTER from $t+1$ parties. We use this fact in the rest of the proof below.

The induction’s base case is $q=j+1\geq 1$ , where each honest party $P_{i}$ runs $\mathsf{Exp}_{j}$ with an input $v_{i}\in\{2^{j}-1,\dots,2^{j+1}-1\}$ . In this base case, the honest parties all input LEFT to $\mathsf{GC}_{2}$ , and thus all output $(\texttt{LEFT},2)$ from it. Then, each honest party $P_{i}$ sets $\mathsf{side}=\texttt{LEFT}$ , sets $v_{i}^{\mathsf{next}}=\min(v_{i},2^{j+1}-1)=v_{i}$ , runs $\mathsf{TC}((2^{j}-1,\dots,2^{j+1}-1))$ with the other parties with the input $v_{i}^{\mathsf{next}}=v_{i}$ , and finally lets its $\mathsf{TC}$ output be its final output. So, $\mathsf{Exp}_{j}$ ’s security follows from $\mathsf{TC}$ ’s security, and $\mathsf{Exp}_{j}$ takes at most $6+6j+1=12q-6j-5$ rounds: $6$ rounds due to $\mathsf{GC}_{2}$ and $6j+1$ rounds due to $\mathsf{TC}$ (since $\mathsf{TC}$ is run on a path of length $2^{j}$ ). However, if the honest parties have a common input, then $\mathsf{TC}$ only takes $6j$ rounds, and thus $\mathsf{Exp}_{j}$ takes $6(j+1)$ rounds instead of $6(j+1)+1$ .

Now, let us consider the cases that might arise when the honest parties run $\mathsf{Exp}_{j}$ with inputs in $\{2^{j}-1,\dots,2^{q}-1\}$ for any $j\in\{q-2,q-3,\dots,0\}$ , with the inductive assumption that $\mathsf{Exp}_{j+1}$ provides edge agreement in $(2^{j+1}-1,\dots,2^{q}-1)$ in at most $6(j+2)$ rounds when run with the common input $2^{j+1}-1$ and at most $12q-6(j+1)-5$ rounds otherwise.

1.

It could be the case that every honest input is less than $2^{j+1}$ . This case is identical to the base case above: The honest parties reach edge agreement in at most $6(j+1)$ rounds if they have a common input and in at most $6(j+1)+1<12q-6j-5$ rounds otherwise.
2.

It could be the case that every honest input is at least $2^{j+1}$ . Then, the honest parties all run $\mathsf{GC}_{2}$ with the input RIGHT, and thus all output $(\texttt{RIGHT},2)$ from it. Then, each honest party $P_{i}$ sets $\mathsf{side}=\texttt{RIGHT}$ , sets $v_{i}^{\mathsf{next}}=\max(v_{i},2^{j+1}-1)=v_{i}$ , runs $\mathsf{Exp}_{j+1}$ with the other parties for edge agreement in the path $(2^{j+1}-1,\dots,2^{q}-1)$ with the input $v_{i}^{\mathsf{next}}=v_{i}$ , and finally lets its $\mathsf{Exp}_{j+1}$ output be its final output. Hence, $\mathsf{Exp}_{j}$ ’s security follows from $\mathsf{Exp}_{j+1}$ ’s security, and $\mathsf{Exp}_{j}$ takes at most $12q-6j-5$ rounds: $6$ rounds due to the initial $\mathsf{GC}_{2}$ , and $\max(6(j+2),12q-6(j+1)-5)=12q-6(j+1)-5$ rounds due to $\mathsf{Exp}_{j+1}$ . The last equality here follows from the fact that $12q\geq 12j+24$ .
3.
The most challenging case is when some honest inputs are below $2^{j+1}$ , while others or not. In this case, the parties run $\mathsf{GC}_{2}$ with different inputs, and so for some $k\in\{\texttt{LEFT},\texttt{RIGHT}\}$ they either all output $(k,2)$ or $(k,1)$ from $\mathsf{GC}_{2}$ , or all output $(k,1)$ or $(\bot,0)$ from $\mathsf{GC}_{2}$ . Below, we say that the corresponding protocol for the graded consensus value $k=\texttt{LEFT}$ is $\mathsf{TC}((2^{j}-1,\dots,2^{j+1}-1))$ , while the corresponding protocol for $k=\texttt{RIGHT}$ is $\mathsf{Exp}_{j+1}$ .
1. (a)
  
  The case where the parties output $(k,2)$ or $(k,1)$ from $\mathsf{GC}_{2}$ for some $k\in\{\texttt{LEFT},\texttt{RIGHT}\}$ is like the two cases we considered above where they all output $(k,2)$ from $\mathsf{GC}_{2}$ , except for that some honest parties run the corresponding protocol with the input $v_{i}^{\mathsf{next}}=v_{i}$ while some others run it with the input $v_{i}^{\mathsf{next}}=2^{j+1}-1$ . As some honest inputs are below $2^{j+1}-1$ while others or not, $2^{j+1}-1$ is in the convex hull of the honest inputs, which means that some honest parties switching their inputs to it does not impact convex validity. So, the honest parties reach edge agreement in at most $12q-6j-5$ rounds by running $\mathsf{GC}_{2}$ in $6$ rounds and then running the corresponding protocol in at most $\max(6j+1,\max(6(j+2),12q-6(j+1)-5))=12q-6(j+1)-5$ rounds.
2. (b)
  If the honest parties all output $(k,1)$ or $(k,\bot)$ from $\mathsf{GC}_{2}$ for some $k\in\{\texttt{LEFT},\texttt{RIGHT}\}$ , then every honest party $P_{i}$ sets $v_{i}^{\mathsf{next}}=2^{j+1}-1$ , which ensures that the honest parties can only run $\mathsf{TC}$ or $\mathsf{Exp}_{j+1}$ with the input $2^{j+1}-1$ and thus only output $2^{j+1}-1$ from them. Hence, an honest party that outputs from $\mathsf{Exp}_{j}$ can only output the valid value $2^{j+1}-1$ , no matter if it outputs on Line 12, 17, 20 or 22. What remains to show is liveness. For this, observe that since $n-t\geq 2t+1$ , there are either $t+1$ honest parties that output $(\bot,0)$ from $\mathsf{GC}_{2}$ , or $t+1$ honest parties that output $(k,1)$ from $\mathsf{GC}_{2}$ .
  1. (i)
    
    In the former case, the $t+1$ honest parties that output $(\bot,0)$ from $\mathsf{GC}_{2}$ multicast CENTER, and so, after one round (i.e. $7<12q-6j-5$ rounds after $\mathsf{Exp}_{j}$ begins) every honest party becomes able to output $2^{j+1}-1$ on Line 22.
  2. (ii)
    
    In the latter case, the $t+1$ honest parties that output $(k,1)$ from $\mathsf{GC}_{2}$ multicast $k\in\{\texttt{LEFT},\texttt{RIGHT}\}$ before running the corresponding protocol, and this allows the honest parties that output $(\bot,0)$ from $\mathsf{GC}_{2}$ to also set $\mathsf{side}=k$ and run the corresponding protocol, albeit with one additional round of delay compared to the parties that output $(k,1)$ from $\mathsf{GC}_{2}$ . Therefore, every honest party that does not output $2^{j+1}-1$ on Line 22 eventually outputs $2^{j+1}-1$ by outputting this from the corresponding protocol. The corresponding protocol (which the honest parties run with the common input $2^{j+1}-1$ ) is either $\mathsf{TC}$ , which takes at most $6j$ rounds, or $\mathsf{Exp}_{j+1}$ , which takes at most $6(j+2)$ rounds. So, every honest party outputs in at most $6+1+6(j+2)=12(j+2)-6j-5\leq 12q-6j-5$ rounds. Here, the first $6$ rounds are due to $\mathsf{GC}_{2}$ , the following $7^{\text{th}}$ round is due to the honest parties that output $(\bot,0)$ from $\mathsf{GC}_{2}$ needing one extra round to learn $k$ , and the final $6(j+2)\leq 12q-6j-12$ rounds are due to the corresponding protocol.

$\hfill\blacktriangleleft$

Theorem 4.

Suppose $\mathsf{Agr}_{\mathsf{N}}$ is a live protocol for edge agreement in $\mathbb{N}$ which for some function $f$ takes at most $f(M)$ rounds when the honest parties run it with inputs in $\{0,\dots,M\}$ . Then, $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ is a live protocol for edge agreement in $\mathbb{N}$ that takes at most $f(5\lfloor\log_{2}(M+1)\rfloor)+\linebreak 6\lfloor\log_{2}(M+1)\rfloor+1$ rounds when the honest parties run it with inputs in $\{0,\dots,M\}$ .

Proof.

Let $V=\{\lfloor\log_{2}(v_{i}+1)\rfloor:P_{i}\text{ is honest}\}$ , let $q_{1}=\min V$ , and let $q_{2}=\max V$ . Observe that $v_{i}\in\{2^{q_{1}}-1,\dots,2^{q_{2}+1}-1\}$ for every honest party $P_{i}$ and that $q_{2}=\lfloor\log_{2}(M+1)\rfloor$ if the maximum honest input is $M$ . The honest parties run $\mathsf{Agr}_{\mathsf{N}}$ with inputs in $\{5q_{1},\dots,5q_{2}\}$ , and so they output adjacent integers in $\{5q_{1},\dots,5q_{2}\}$ from it, in at most $f(5q_{2})$ rounds.

If $q_{1}=q_{2}$ , then the honest parties all run $\mathsf{Agr}_{\mathsf{N}}$ with the common input $5q_{2}$ , and thus they all output $5q_{2}$ from it. Consequently, each honest party $P_{i}$ sets $(k_{i},r_{i})=(q_{2},0)$ and obtains its final output from a common instance of $\mathsf{TC}((2^{q_{2}}-1,\dots,2^{q_{2}+1}-1))$ which it runs with the input $v_{i}^{\mathsf{next}}=\min(\max(v_{i},2^{q_{2}}-1),2^{q_{2}+1}-1)=v_{i}\in\{2^% {q_{2}}-1,\dots,2^{q_{2}+1}-1\}$ . Edge agreement thus follows from $\mathsf{TC}$ , in $6q_{2}+1$ more rounds.

For the rest of the proof, we assume $q_{1}<q_{2}$ . Observe that the boundary values $q_{1}$ and $q_{2}$ arise from some honest inputs $v_{i},v_{j}$ being such that $\lfloor\log_{2}(v_{i}+1)\rfloor=q_{1}$ and $\lfloor\log_{2}(v_{j}+1)\rfloor=q_{2}$ . These equalities respectively imply $v_{i}<2^{q_{1}+1}-1$ and $v_{j}\geq 2^{q_{2}}-1$ , which means that every integer in $\{2^{q_{1}+1}-1,\dots,2^{q_{2}}-1\}$ is in the convex hull of the honest parties’ inputs.

When an honest party $P_{i}$ outputs $5k_{i}+r_{i}$ from $\mathsf{Agr}_{\mathsf{N}}$ , it lets $v_{i}^{\mathsf{next}}=\min(\max(v_{i},2^{k_{i}}-1),2^{k_{i}+1}-1)$ if $r_{i}=0$ , and lets $v_{i}^{\mathsf{next}}=2^{k_{i}+1}-1$ otherwise. Let us show that in every possible case $P_{i}$ chooses a valid $v_{i}^{\mathsf{next}}$ ; that is, $P_{i}$ sets $v_{i}^{\mathsf{next}}$ to a value which is inside the convex hull of the honest inputs. If $r_{i}=0$ , then $q_{1}\leq k_{i}\leq q_{2}$ , and there are three cases we must consider: If $v_{i}<2^{k_{i}}-1$ then $v_{i}^{\mathsf{next}}=2^{k_{i}}-1$ is valid since $2^{k_{i}}-1$ is between the valid values $v_{i}$ and $2^{q_{2}}-1$ , if $v_{i}>2^{k_{i}+1}-1$ then $v_{i}^{\mathsf{next}}=2^{k_{i}+1}-1$ is valid since $2^{k_{i}+1}-1$ is between the valid values $2^{q_{1}+1}-1$ and $v_{i}$ , and finally if $2^{k_{i}}-1\leq v_{i}\leq 2^{k_{i}+1}-1$ then $v_{i}^{\mathsf{next}}=v_{i}$ is valid as well. Meanwhile, if $r_{i}>0$ , then by $5q_{1}\leq 5k_{i}+r_{i}\leq 5q_{2}$ we have $q_{1}\leq k_{i}\leq q_{2}-1$ , which makes $v_{i}^{\mathsf{next}}=2^{k_{i}+1}-1\in\{2^{q_{1}+1}-1,\dots,2^{q_{2}}-1\}$ valid.

Convex validity follows from the fact that every honest party $P_{i}$ either directly outputs the valid value $2^{k_{i}+1}-1$ or obtains its output from a $\mathsf{TC}$ instance for which the honest parties can only acquire valid inputs. Note that the honest parties do not run $\mathsf{TC}$ with out-of-range inputs: The value $2^{k_{i}+1}-1$ which a party $P_{i}$ inputs to $\mathsf{TC}((2^{k_{i}}-1,\dots,2^{k_{i}+1}-1))$ if $r_{i}\in\{1,2\}$ or $\mathsf{TC}((2^{k_{i}+1}-1,\dots,2^{k_{i}+2}-1))$ if $r_{i}\in\{3,4\}$ is in range for both $\mathsf{TC}((2^{k_{i}}-1,\dots,2^{k_{i}+1}-1))$ and $\mathsf{TC}((2^{k_{i}+1}-1,\dots,2^{k_{i}+1}-1))$ , and the value $\min(\max(v_{i},2^{k_{i}}-1),2^{k_{i}+1}-1)$ which a party $P_{i}$ inputs to $\mathsf{TC}((2^{k_{i}}-1,\dots,2^{k_{i}+1}-1))$ if $r_{i}=0$ is in-range as well.

The initial $\mathsf{Agr}_{\mathsf{N}}$ guarantees that there exists some $v=5k+r$ where $q_{1}\leq k\leq q_{2}-1$ and $0\leq r\leq 4$ such that every honest party outputs either $v$ or $v+1$ from it. Based on this, let us prove the edge agreement and liveness properties of $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ via case analysis on $r$ .

1.

If $r=0$ , then the honest parties all run $\mathsf{TC}((2^{k}-1,\dots,2^{k+1}-1))$ with in-range valid inputs, and obtain their final outputs from it. Edge agreement in $\mathbb{N}$ thus follows from $\mathsf{TC}((2^{k}-1,\dots,2^{k+1}-1))$ , in $6k+1$ more rounds.
2.

If $r=1$ , then the honest parties all run $\mathsf{TC}((2^{k}-1,\dots,2^{k+1}-1))$ with the common input $2^{k+1}-1$ , and thus all output $2^{k+1}-1$ from it in $6k$ rounds. The honest parties $P_{i}$ that have $r_{i}=1$ output $2^{k+1}-1$ from $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ after they output $2^{k+1}-1$ from $\mathsf{TC}$ , while those that have $r_{i}=2$ output $2^{k+1}-1$ directly after they output from $\mathsf{Agr}_{\mathsf{N}}$ .
3.

If $r=2$ , then every honest party $P_{i}$ has $r_{i}\in\{2,3\}$ , which leads to it directly outputting $2^{k+1}-1$ after it outputs from $\mathsf{Agr}_{\mathsf{N}}$ . The fact that the honest parties $P_{i}$ with $r_{i}=2$ run $\mathsf{TC}((2^{k}-1,\dots,2^{k+1}-1))$ while those with $r_{i}=3$ run $\mathsf{TC}((2^{k+1}-1,\dots,2^{k+2}-1))$ is not an issue as none of the honest parties care about their $\mathsf{TC}$ outputs.
4.

If $r=3$ , then the honest parties run $\mathsf{TC}((2^{k+1}-1,\dots,2^{k+2}-1))$ with the common input $2^{k+1}-1$ , and thus all output $2^{k+1}-1$ from it in $6(k+1)$ rounds. The honest parties $P_{i}$ that have $r_{i}=4$ output $2^{k+1}-1$ from $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ after they output $2^{k+1}-1$ from $\mathsf{TC}$ , while those that have $r_{i}=3$ output $2^{k+1}-1$ directly after they output from $\mathsf{Agr}_{\mathsf{N}}$ .
5.

If $r=4$ , then every honest party $P_{i}$ (both if $(k_{i},r_{i})=(k,r)$ and if $(k_{i},r_{i})=(k+1,0)$ ) runs $\mathsf{TC}((2^{k+1}-1,\dots,2^{k+2}-1))$ with an in-range valid input, and obtains its final output from it. Edge agreement thus follows from $\mathsf{TC}((2^{k+1}-1,\dots,2^{k+2}-1))$ , in $6(k+1)+1$ more rounds.

Note that in all the cases above, $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ takes at most $6q_{2}+1$ rounds after $\mathsf{Agr}_{\mathsf{N}}$ . Hence, $\mathsf{2\textsf{-}Step}(\mathsf{Agr}_{\mathsf{N}})$ takes at most $f(5q_{2})+6q_{2}+1$ rounds. This is the round complexity stated in the theorem since $q_{2}=\lceil\log_{2}(M+1)\rceil$ by definition. $\hfill\blacktriangleleft$

Theorem 5.

If $\mathsf{Agr}_{\mathsf{N}}$ is a live protocol for edge agreement in $\mathbb{N}$ , then $\mathsf{Agr}_{\mathsf{Z}}(\mathsf{Agr}_{\mathsf{N}})$ is a live protocol for edge agreement in $\mathbb{Z}$ .

Proof.

If the honest parties all have inputs in $\mathbb{N}$ , then every honest party $P_{i}$ runs $\mathsf{GC}_{2}$ with the input $1$ , outputs $(1,2)$ from $\mathsf{GC}_{2}$ , lets $v_{i}^{\mathsf{next}}=\max(0,1\cdot v_{i})=v_{i}$ , runs $\mathsf{Agr}_{\mathsf{N}}$ with the input $v_{i}^{\mathsf{next}}=v_{i}$ , and finally outputs $1\cdot y=y$ from $\mathsf{Agr}_{\mathsf{Z}}(\mathsf{Agr}_{\mathsf{N}})$ when it outputs $y$ from $\mathsf{Agr}_{\mathsf{N}}$ . Thus, $\mathsf{Agr}_{\mathsf{Z}}(\mathsf{Agr}_{\mathsf{N}})$ ’ security follows from $\mathsf{Agr}_{\mathsf{N}}$ ’s security.

Similarly, if the honest parties all have negative inputs, then every honest party $P_{i}$ runs $\mathsf{GC}_{2}$ with the input $-1$ , outputs $(-1,2)$ from $\mathsf{GC}_{2}$ , lets $v_{i}^{\mathsf{next}}=\max(0,-1\cdot v_{i})=-v_{i}$ , runs $\mathsf{Agr}_{\mathsf{N}}$ with the input $v_{i}^{\mathsf{next}}=-v_{i}$ , and finally outputs $-1\cdot y=-y$ from $\mathsf{Agr}_{\mathsf{Z}}(\mathsf{Agr}_{\mathsf{N}})$ when it outputs $y$ from $\mathsf{Agr}_{\mathsf{N}}$ . Again, $\mathsf{Agr}_{\mathsf{Z}}(\mathsf{Agr}_{\mathsf{N}})$ ’s security follows from $\mathsf{Agr}_{\mathsf{N}}$ ’s security. This is because by symmetry $\mathsf{Agr}_{\mathsf{N}}$ behaves as an edge agreement protocol for $(\dots,-1,0)$ when the parties mirror (sign-flip) their inputs for it and outputs from it.

Finally, there is the case where some honest parties have negative inputs while others do not. In this case, the honest parties run $\mathsf{GC}_{2}$ with different inputs, and so for some $k\in\{1,-1\}$ they either all output $(k,2)$ or $(k,1)$ from $\mathsf{GC}_{2}$ , or all output $(k,1)$ or $(\bot,0)$ from $\mathsf{GC}_{2}$ . The case where they all output $(k,2)$ or $(k,1)$ from $\mathsf{GC}_{2}$ is similar to the cases above, though with some honest parties $P_{i}$ running $\mathsf{Agr}_{\mathsf{N}}$ with the input $v_{i}^{\mathsf{next}}=0$ rather than $v_{i}^{\mathsf{next}}=kv_{i}$ . As $0$ is in the convex hull of the honest inputs, this does not impact validity, and the honest parties safely reach edge agreement via $\mathsf{Agr}_{\mathsf{N}}$ , with input/output mirroring if $k=-1$ and without mirroring if $k=1$ . Meanwhile, if the honest parties all output $(k,1)$ or $(\bot,0)$ from $\mathsf{GC}_{2}$ , then they all run $\mathsf{Agr}_{\mathsf{N}}$ with the input $0$ . So, the honest parties with the $\mathsf{GC}_{2}$ output $(k,1)$ output $k\cdot 0=0$ from $\mathsf{Agr}_{\mathsf{Z}}(\mathsf{Agr}_{\mathsf{N}})$ after outputting $0$ from $\mathsf{Agr}_{\mathsf{N}}$ , while those with the $\mathsf{GC}_{2}$ output $(\bot,0)$ output $0$ from $\mathsf{Agr}_{\mathsf{Z}}(\mathsf{Agr}_{\mathsf{N}})$ directly without caring about their $\mathsf{Agr}_{\mathsf{N}}$ outputs. $\hfill\blacktriangleleft$

[bib.bib1] [1] Ittai Abraham, Yonatan Amit, and Danny Dolev. Optimal resilience asynchronous approximate agreement. In Proceedings of the 8th International Conference on Principles of Distributed Systems, OPODIS ’04, pages 229–239, Berlin, Heidelberg, 2004. Springer-Verlag. doi:10.1007/11516798_17.

[bib.bib2] [2] Ittai Abraham, T-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication complexity of byzantine agreement, revisited. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC ’19, pages 317–326, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3293611.3331629.

[bib.bib3] [3] Nicolas Alhaddad, Sourav Das, Sisi Duan, Ling Ren, Mayank Varia, Zhuolun Xiang, and Haibin Zhang. Balanced byzantine reliable broadcast with near-optimal communication and improved computation. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC ’22, pages 399–417, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3519270.3538475.

[bib.bib4] [4] Hagit Attiya and Jennifer L. Welch. Multi-Valued Connected Consensus: A New Perspective on Crusader Agreement and Adopt-Commit. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023), volume 286 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:23, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.OPODIS.2023.6.

[bib.bib5] [5] Akhil Bandarupalli, Adithya Bhat, Saurabh Bagchi, Aniket Kate, Chen-Da Liu-Zhang, and Michael K. Reiter. Delphi: Efficient Asynchronous Approximate Agreement for Distributed Oracles. In 2024 54th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 456–469, Los Alamitos, CA, USA, June 2024. IEEE Computer Society. doi:10.1109/DSN58291.2024.00051.

[bib.bib6] [6] Jon Louis Bentley and Andrew Chi-Chih Yao. An almost optimal algorithm for unbounded searching. Information Processing Letters, 5(3):82–87, 1976. doi:10.1016/0020-0190(76)90071-5.

[bib.bib7] [7] Erica Blum, Jonathan Katz, and Julian Loss. Synchronous consensus with optimal asynchronous fallback guarantees. In Theory of Cryptography — TCC 2019, Cham, Switzerland, 2019. Springer International Publishing. doi:10.1007/978-3-030-36030-6_6.

[bib.bib8] [8] Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2), 1987. doi:10.1016/0890-5401(87)90054-X.

[bib.bib9] [9] Jing Chen and Silvio Micali. Algorand: A secure and efficient distributed ledger. Theor. Comput. Sci., 777(C):155–183, July 2019. doi:10.1016/j.tcs.2019.02.001.

[bib.bib10] [10] B. A. Coan. A compiler that increases the fault tolerance of asynchronous protocols. IEEE Trans. Comput., 37(12):1541–1553, December 1988. doi:10.1109/12.9732.

[bib.bib11] [11] Andrei Constantinescu, Diana Ghinea, Roger Wattenhofer, and Floris Westermann. Convex Consensus with Asynchronous Fallback. In 38th International Symposium on Distributed Computing (DISC 2024), volume 319 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:23, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2024.15.

[bib.bib12] [12] Giovanni Deligios and Mose Mizrahi Erbes. Closing the efficiency gap between synchronous and network-agnostic consensus. In Advances in Cryptology – EUROCRYPT 2024, pages 432–461, Cham, 2024. Springer Nature Switzerland. doi:10.1007/978-3-031-58740-5_15.

[bib.bib13] [13] D. Dolev and H. R. Strong. Authenticated algorithms for byzantine agreement. SIAM Journal on Computing, 12(4):656–666, 1983. doi:10.1137/0212045.

[bib.bib14] [14] Danny Dolev, Nancy A. Lynch, Shlomit S. Pinter, Eugene W. Stark, and William E. Weihl. Reaching approximate agreement in the presence of faults. J. ACM, 33(3):499–516, May 1986. doi:10.1145/5925.5931.

[bib.bib15] [15] Danny Dolev and Rüdiger Reischuk. Bounds on information exchange for byzantine agreement. J. ACM, 32(1):191–204, January 1985. doi:10.1145/2455.214112.

[bib.bib16] [16] Maya Dotan, Gilad Stern, and Aviv Zohar. Validated byzantine asynchronous multidimensional approximate agreement, 2022. doi:10.48550/arXiv.2211.02126.

[bib.bib17] [17] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374–382, April 1985. doi:10.1145/3149.214121.

[bib.bib18] [18] Matthias Fitzi, Chen-Da Liu-Zhang, and Julian Loss. A new way to achieve round-efficient byzantine agreement. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, PODC ’21, pages 355–362, New York, NY, USA, 2021. Association for Computing Machinery. doi:10.1145/3465084.3467907.

[bib.bib19] [19] Marc Fuchs, Diana Ghinea, and Zahra Parsaeian. Brief announcement: Towards round-optimal approximate agreement on trees. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 54–57, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3732772.3733555.

[bib.bib20] [20] Diana Ghinea, Vipul Goyal, and Chen-Da Liu-Zhang. Round-optimal byzantine agreement. In Advances in Cryptology – EUROCRYPT 2022, pages 96–119, Cham, 2022. Springer International Publishing. doi:10.1007/978-3-031-06944-4_4.

[bib.bib21] [21] Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Optimal synchronous approximate agreement with asynchronous fallback. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC ’22, pages 70–80, New York, NY, USA, 2022. Association for Computing Machinery. doi:10.1145/3519270.3538442.

[bib.bib22] [22] Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Multidimensional approximate agreement with asynchronous fallback. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’23, pages 141–151, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3558481.3591105.

[bib.bib23] [23] Diana Ghinea, Chen-Da Liu-Zhang, and Roger Wattenhofer. Communication-optimal convex agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’25, pages 39–49, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3732772.3733551.

[bib.bib24] [24] Camille Jordan. Sur les assemblages de lignes. Journal für die reine und angewandte Mathematik, 70:185–190, 1869. URL: http://eudml.org/doc/148084.

[bib.bib25] [25] Simon Holmgaard Kamp. A new way to achieve round-efficient asynchronous byzantine agreement. Cryptology ePrint Archive, Paper 2025/143, 2025. URL: https://eprint.iacr.org/2025/143.

[bib.bib26] [26] Hammurabi Mendes, Maurice Herlihy, Nitin Vaidya, and Vijay K. Garg. Multidimensional agreement in byzantine systems. Distrib. Comput., 28(6):423–441, December 2015. doi:10.1007/s00446-014-0240-5.

[bib.bib27] [27] Mose Mizrahi Erbes and Roger Wattenhofer. Brief Announcement: Asynchronous Approximate Agreement with Quadratic Communication. In Dariusz R. Kowalski, editor, 39th International Symposium on Distributed Computing (DISC 2025), volume 356 of Leibniz International Proceedings in Informatics (LIPIcs), pages 61:1–61:7, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2025.61.

[bib.bib28] [28] Mose Mizrahi Erbes and Roger Wattenhofer. Quit-Resistant Reliable Broadcast and Efficient Terminating Gather. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024), volume 324 of Leibniz International Proceedings in Informatics (LIPIcs), pages 15:1–15:22, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.OPODIS.2024.15.

[bib.bib29] [29] Thomas Nowak and Joel Rybicki. Byzantine Approximate Agreement on Graphs. In 33rd International Symposium on Distributed Computing (DISC 2019), volume 146 of Leibniz International Proceedings in Informatics (LIPIcs), pages 29:1–29:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.DISC.2019.29.

[bib.bib30] [30] A simple introduction to centroid decomposition. A Simple Blog, 2020. Accessed: 2025-08-15. URL: https://robert1003.github.io/2020/01/16/centroid-decomposition.html.

Asynchronous Approximate Agreement with Quadratic Communication

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Model & Definitions

Edge Agreement in a Tree

Graded Consensus

3 Overview & Contributions

4 Edge Agreement in a Tree

Proposition 1.

Proof.

Theorem 2.

Proof.

Complexity of 𝗧𝗖⁢(𝑻).

An Alternative Way.

5 Edge Agreement in Infinite Paths

5.1 Edge Agreement in ℕ

Theorem 3.

Complexity of 𝗘𝘅𝗽𝟎.

5.2 Nearly Halving the Round Complexity

Theorem 4.

Complexity of 𝟮⁢-⁢𝗦𝘁𝗲𝗽⁢(𝗘𝘅𝗽𝟎).

5.3 Edge Agreement in ℤ

Theorem 5.

Complexity.

6 Termination

Theorem 6.

Termination for edge agreement in ℤ.

Termination for edge agreement in trees.

7 Extension to Real Numbers

Theorem 7.

Proof.

Future Work.

References

Appendix A Graded Consensus Protocols

A.1 1-Graded Consensus

Theorem 8.

Proof.

Complexity.

A.2 Grade Doubling

Theorem 9.

Proof.

Complexity.

Theorem 10.

Proof.

Complexity.

Appendix B The Termination Protocol 𝗧𝗲𝗿𝗺

Theorem 6.

Proof.

Appendix C Skipped Proofs

Theorem 3.

Proof.

Theorem 4.

Proof.

Theorem 5.

Proof.

Complexity of $\mathsf{TC}(T)$ .

5.1 Edge Agreement in $\mathbb{N}$

Complexity of $\mathsf{Exp}_{0}$ .

Complexity of $\mathsf{2\textsf{-}Step}(\mathsf{Exp}_{0})$ .

5.3 Edge Agreement in $\mathbb{Z}$

Termination for edge agreement in $\mathbb{Z}$ .

Appendix B The Termination Protocol $\mathsf{Term}$