Parallel and Distributed Systems Group

From Few to Many Faults: Optimal Adaptive Byzantine Agreement

Reading group: Aymen Kabil presented "From Few to Many Faults: Optimal Adaptive Byzantine Agreement" (PODC'26) at 1D23 the 6/11/2026 at 10h30.

Abstract

Achieving agreement among distributed parties is a fundamental task in modern systems, underpinning applications such as consen- sus 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 𝑛 parties tolerating up to 𝑡 Byzantine faults, out of which only 𝑓 ≤ 𝑡 are actually faulty, we give the following results: • When 𝑡 = Ω(𝑛), in the synchronous (resp. partially syn- chronous) setting, with optimal resiliency 𝑡 < 𝑛/2 (resp. 𝑡 < 𝑛/3), we describe a deterministic protocol with optimal communication complexity O(𝑛 · (𝑓 + 1)) and optimal round complexity O(𝑓 + 1). • Building upon this previous result, when 𝑡 = 𝑜 (𝑛), for both the synchronous and partially synchronous setting, we de- scribe a deterministic protocol with near-optimal commu- nication complexity eO(𝑛 + 𝑡 · 𝑓 ) and near-optimal round complexity eO(𝑓 + 1). Our approach relies on a novel use of dispersers to efficiently disseminate a value. • For the asynchronous setting, we show a Ω(𝑛 + 𝑡2) lower bound in expectation and provide a randomized protocol with near-optimal eO(𝑛 + 𝑡2) communication complexity and O(1) round complexity in expectation.