Paper 2024/822

Early Stopping Byzantine Agreement in $(1+ϵ)\cdot f$ Rounds

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 $$ rounds, where $$ is a fixed constant. For example, for all $$, our protocol runs in at most $$ rounds (where $$), improving (for large $$) upon the best previous early stopping deterministic broadcast protocol by Perry and Toueg 1984, which terminates in $$ rounds. Additionally, our second protocol is randomized, ensuring termination in an expected constant number of rounds and achieving early stopping in $$ rounds in the worst case. This marks a significant improvement over a similar result by Goldreich and Petrank 1990, which always requires an expected constant number of rounds and $$ rounds in the worst case, i.e., does not have the early stopping property.