2026-07-22T13:50:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25189 2026-03-19T12:59:23Z ddc:004 open_access

Asynchronous Approximate Agreement with Quadratic Communication Mizrahi Erbes, Mose Wattenhofer, Roger Approximate agreement byzantine fault tolerance communication complexity 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 < n/3 by forcing the parties to reliably broadcast their messages and thus preventing inconsistent byzantine behavior. This costs Θ(n²) messages per reliable broadcast, or Θ(n³) messages per protocol iteration. In this work, we forgo reliable broadcast to achieve asynchronous approximate agreement against t < n/3 faults with quadratic communication. In a tree with the maximum degree Δ and the centroid decomposition height h, we achieve edge agreement (agreement on two adjacent vertices) in at most 6h + 1 rounds with 𝒪(n²) messages of size 𝒪(log Δ + 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 ℤ, again by using 2-graded consensus. Finally, we show that our edge agreement protocol enables approximate agreement in ℝ (with outputs that are at most some small parameter ε > 0 apart) in 6log₂M/(ε) + 𝒪(log log M/(ε)) rounds with 𝒪(n²) messages of size 𝒪(log log M/(ε)) per round, where M is the maximum non-byzantine input magnitude. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mose Mizrahi Erbes and Roger Wattenhofer 2026 Is Part Of LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2025.16 urn:nbn:de:0030-drops-251890 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode