Welcome to the resource topic for 2024/822
Title:
Early Stopping Byzantine Agreement in (1+\epsilon)\cdot f Rounds
Authors: Fatima Elsheimy, Julian Loss, Charalampos Papamanthou
Abstract:In this paper, we present two early stopping Byzantine agreement protocols in the authenticated setting against a corrupt minority t < n/2, where t represents the maximum number of malicious parties. Early stopping protocols ensure termination within a number of rounds determined solely by the actual number of malicious nodes f present during execution, irrespective of t.
Our first protocol is deterministic and ensures early stopping termination in (d+5) \cdot (\lfloor f/d \rfloor +3) rounds, where d is a fixed constant. For example, for all d\ge 6, our protocol runs in at most (1+\epsilon )\cdot f rounds (where 0<\epsilon<1), improving (for large f) upon the best previous early stopping deterministic broadcast protocol by Perry and Toueg~\cite{Perry}, which terminates in min(2f+4,2t+2) rounds. Additionally, our second protocol is randomized, ensuring termination in an expected constant number of rounds and achieving early stopping in (d+9) \cdot (\lfloor f/d \rfloor +2) rounds in the worst case. This marks a significant improvement over a similar result by Goldreich and Petrank[GOLDREICH1990], which always requires an expected constant number of rounds and O(t) rounds in the worst case, i.e., does not have the early stopping property.
ePrint: https://eprint.iacr.org/2024/822
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 .