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 < n3 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 ₂ D iterations of a multivalued graded consensus variant for which we design an efficient protocol. This results in a O (1) -round protocol for -agreement in 0, 1 with O (n²1) messages and O (n²11) 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.