Anton Paramonov

Andrei Constantinescu, Marc Dufay, Anton Paramonov et al. · eth-zurich

Achieving agreement among distributed parties is a fundamental task in modern systems, underpinning applications such as consensus in blockchains, coordination in cloud infrastructure, and fault tolerance in critical services. However, this task can be intensive, often requiring a large number of messages to be exchanged as well as many rounds of communication, especially in the presence of Byzantine faults. This makes efficiency a central challenge in the design of practical agreement protocols. In this paper, we study the problem of Binary Agreement and give protocols that are simultaneously optimal in both message and round complexity, parameterized by the actual number of Byzantine faults. In contrast to previous works, we demonstrate that optimal message complexity can be achieved without sacrificing latency. Concretely, for a system of $n$ parties tolerating up to $t$ Byzantine faults, out of which only $f \leq t$ are actually faulty, we give the following results: When $t = Ω(n)$, in the synchronous (resp. partially synchronous) setting, with optimal resiliency $t < n/2$ (resp. $t < n/3$), we describe a deterministic protocol with optimal communication complexity $O(n \cdot (f+1))$ and optimal round complexity $O(f + 1)$. Building upon this previous result, when $t = o(n)$, for both the synchronous and partially synchronous setting, we describe a deterministic protocol with near-optimal communication complexity $\widetilde{O}(n + t\cdot f)$ and near-optimal round complexity $\widetilde{O}(f+1)$. Our approach relies on a novel use of dispersers to efficiently disseminate a value. For the asynchronous setting, we show a $Ω(n + t^2)$ lower bound in expectation and provide a randomized protocol with near-optimal $\widetilde{O}(n + t^2)$ communication complexity and $O(1)$ round complexity in expectation.

Marc Dufay, Diana Ghinea, Anton Paramonov

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.

Bernhard Haeupler, Anton Paramonov

We study and further develop powerful general-purpose schemes to maintain random assignments under adversarial dynamic changes. The goal is to maintain assignments that are (approximately) distributed similarly as a completely fresh resampling of all assignments after each change, while doing only a few resamples per change. This becomes particularly interesting and challenging when dynamics are controlled by an adaptive adversary. Our work builds on and further develops the proactive resampling technique [Bhattacharya, Saranurak, and Sukprasert ESA'22]. We identify a new ``temporal selection'' attack that adaptive adversaries can use to cause biases, even against proactive resampling. We propose a new ''temporal aggregation'' principle that algorithms should follow to counteract these biases, and present two powerful new resampling schemes based on this principle. We give various applications of our new methods. The main one in maintaining proper coloring of the graph under adaptive adversarial modifications: we maintain $O(Δ)$ coloring for general graphs with maximum degree $Δ$ and $O(\fracΔ{\ln Δ})$ coloring for triangle free graphs, both with sublinear in the number of vertices average work per modification. Other applications include efficiently maintaining random walks in dynamically changing graphs.