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

Summary

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) · ([f /d] + 2) + 2 rounds, where d is a fixed constant. For example, for all d ≥ 6, our protocol runs in at most (1 + ϵ) · f rounds (where 0 < ϵ < 1), improving (for large f) upon the best previous early stopping deterministic broadcast protocol by Perry and Toueg [1], 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) · ([f /d] + 1) + 2 rounds in the worst case. This marks a significant improvement over a similar result by Goldreich and Petrank. [2], 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.