Asynchronous Approximate Agreement with Quadratic Communication

We consider an asynchronous network of n message-sending parties, up to t of which are byzantine. We study approximate agreement, where the parties obtain approximately equal outputs in the convex hull of their inputs. The seminal protocol of Abraham, Amit and Dolev [OPODIS '04] achieves approximate agreement in R with the optimal resilience t < n/3 by making each party reliably broadcast its input. This takes Ω(n²) messages per reliable broadcast, or Ω(n³) messages in total. In this work, we present optimally resilient asynchronous approximate agreement protocols which forgo reliable broadcast and thus require communication proportional to n² instead of n³. First, we achieve ω-dimensional barycentric agreement with O(ω n²) small messages. Then, we achieve edge agreement in a tree of diameter D with log₂ D iterations of a multivalued graded consensus variant for which we design an efficient protocol. This results in a O(log1/ε)-round protocol for ε-agreement in $[0, 1]$ with O(n²log1/ε) messages and O(n²log1/εloglog1/ε) bits of communication, improving over the state of the art which matches this complexity only when the inputs are all either $0$ or $1$. Finally, we extend our edge agreement protocol to achieve edge agreement in Z and thus ε-agreement in R with quadratic communication, in O(/ε) rounds where M is the maximum honest input magnitude.