Welcome to the resource topic for 2023/1139
Title:
Optimal Load-Balanced Scalable Distributed Agreement
Authors: Yuval Gelles, Ilan Komargodski
Abstract:We consider the fundamental problem of designing classical consensus-related distributed abstractions for large-scale networks, where the number of parties can be huge. Specifically, we consider tasks such as Byzantine Agreement, Broadcast, and Committee Election, and our goal is to design scalable protocols in the sense that each honest party processes and sends a number of bits which is sub-linear in n, the total number of parties.
In this work, we construct the first such scalable protocols for all of the
above tasks. In our protocols, each party processes and sends \tilde O (\sqrt n) bits throughout \tilde O (1) rounds of communication, and correctness is guaranteed for at most 1/3-\epsilon fraction of static byzantine corruptions for every constant \epsilon>0 (in the full information model). All previous protocols for the considered agreement tasks were non-scalable, either because the communication complexity was linear or because the computational complexity was super polynomial.
We complement our result with a matching lower bound showing that any
Byzantine Agreement protocol must have \Omega(\sqrt n) complexity in our model. Previously, the state of the art was the well-known \tilde\Omega(\sqrt[3]{n}) lower bound of Holtby, Kapron, and King (Distributed Computing, 2008).
ePrint: https://eprint.iacr.org/2023/1139
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 .