General Convex Agreement with Near-Optimal Communication
For distributed systems requiring robust aggregation (e.g., sensor fusion, robust learning), this work narrows the communication gap between convex agreement and standard Byzantine agreement, providing the first near-optimal protocols.
This work presents deterministic synchronous Byzantine agreement protocols for convex agreement that achieve near-optimal communication complexity: O(L n log n) for finite convexity spaces and O(L n^{1+o(1)}) for Euclidean spaces, with optimal O(n) round complexity. The protocols use extractor graphs for robust committee assignment against adaptive adversaries.
Byzantine Agreement (BA) considers a setting of $n$ parties out of which up to $t$ can be byzantine (malicious), and requires the honest parties to agree on an input subject to a condition called \emph{validity}: if all honest parties have input $v$, the output agreed upon must be $v$. Convex Agreement (CA) strengthens BA by requiring the output agreed upon to lie in the convex hull of the honest parties' inputs. This validity condition captures aggregation tasks, such as robust learning and sensor fusion, where honest inputs may differ but should still constrain the final decision. Existing protocols for CA over general convexity spaces require at least $O(L \cdot n^2)$ bits of communication for $L$-bit inputs, leaving a gap with BA's $Ω(L \cdot n)$ lower bound. We investigate this gap, and we present deterministic synchronous CA protocols with near-optimal communication complexity in the long-message regime. When $L=Ω(n\cdotκ)$, where $κ$ is a security parameter, our protocols use $\mathcal{O}(L\cdot n\log n)$ bits of communication for finite convexity spaces and $\mathcal{O}(L\cdot n^{1+o(1)})$ communication for Euclidean spaces $\mathbb{R}^d$. Our protocols also have asymptotically optimal round complexity $\mathcal{O}(n)$. If an upper bound $L$ on the honest inputs' length in bits is known in advance, we achieve near-optimal resilience $t<n/(ω+\varepsilon)$ for any constant $\varepsilon>0$, where $ω$ is the Helly number of the convexity space. When no such bound is known, we achieve resilience $t<n/(ω+\varepsilon+1)$. As a sample application, we show how our protocols can be used to obtain efficient solutions for parallel instances of BA. Our main technical contribution is the use of extractor graphs to obtain a deterministic assignment of parties to committees, which is robust against adaptive adversaries.