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 .