Welcome to the resource topic for 2025/1318
Title:
Lifeline: Optimal Byzantine Agreement Under Minimal Synchrony
Authors: Yuval Efron, Ling Ren
Abstract:The synchrony model allows Byzantine Agreement (BA) protocols to be deterministic, tolerate minority
faults, and achieve the asymptotically optimal O(n) rounds, and O(n^2) bits of communication where n is the number of parties.
We study the deterministic BA problem in a model in which every communication link is either synchronous or partially synchronous. Our main result for this model is that feasibility implies optimality: For every \frac{n}{3}\leq f<\frac{n}{2}, the minimal network conditions required for BA to be solvable against f byzantine faults, are also sufficient for it to be solvable optimally, i.e., with O(f) rounds and O(f^2) communication. In particular, BA against minority byzantine faults can be solved when the synchronous links in the network form a mere path (f synchronous links) as efficiently (up to constant factors) as when all communication links are synchronous (\Omega(f^2) synchronous links).
ePrint: https://eprint.iacr.org/2025/1318
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .