Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Events

The Taub Faculty of Computer Science Events and Talks

Communication Abstractions for Optimal Byzantine Resilience
event speaker icon
Itay Flam (M.Sc. Thesis Seminar)
event date icon
Wednesday, 26.11.2025, 11:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. Hagit Attiya

We study communication abstractions for asynchronous Byzantine fault tolerance with optimal failure resilience, where n > 3f. Two classic patterns—canonical asynchronous rounds and communication-closed layers—have long been considered as general frameworks for designing distributed algorithms, making asynchronous executions appear synchronous and enabling modular reasoning. We show that these patterns are inherently limited in the critical resilience regime 3f < n ≤5f. Several key tasks—such as approximate and crusader agreement, reliable broadcast and gather—cannot be solved by bounded-round canonical-round algorithms, and are unsolvable if communication closure is imposed. These results explain the historical difficulty of achieving optimal-resilience algorithms within round-based frameworks. On the positive side, we show that the gather abstraction admits constant-time solutions with optimal resilience (n > 3f ), and supports modular reductions. Specifically, we present the first optimally-resilient algorithm for binding connected consensus by reducing it to gather. For completeness, we present an optimally-resilient algorithm for gather which terminates in constant time. Our results demonstrate that while round-based abstractions are analytically convenient, they obscure the true complexity of Byzantine fault-tolerant algorithms. Richer communication patterns such as gather provide a better foundation for modular, optimal-resilience design.