# Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity

arXiv: https://arxiv.org/abs/1504.02547 · HTML: https://mlsanity.com/paper/1504.02547/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Apr 2015.

## Built on by (most cited first, 1 of 1)

- [VALID: a Validated Algorithm for Learning in Decentralized Networks with Possible Adversarial Presence](https://mlsanity.com/paper/2405.07316/) (2024)

## Abstract (arXiv)

We provide the first protocol that solves Byzantine agreement with optimal early stopping (minf+2,t+1 rounds) and optimal resilience (n>3t) using polynomial message size and computation. All previous approaches obtained sub-optimal results and used resolve rules that looked only at the immediate children in the EIG (Exponential Information Gathering) tree. At the heart of our solution are new resolve rules that look at multiple layers of the EIG tree.