Search papers, labs, and topics across Lattice.
This paper establishes a new lower bound on the worst-case expected round complexity of randomized synchronous Byzantine Agreement protocols in a full-information, strongly adaptive adversary model, demonstrating that it is \(\Omega\left(\frac{t^2}{n\log(n+1)}\right)\) for \(t\) corrupt parties. This result improves upon the previous bound of \(\Omega(\frac{t}{\sqrt{n\log n}})\) and aligns with recent upper bounds, providing a more comprehensive understanding of the complexities involved in Byzantine Agreement. The authors employ a novel multi-round concentration lemma and leverage established tools to derive their findings, significantly advancing the theoretical framework of distributed consensus protocols.
Every randomized Byzantine Agreement protocol faces a fundamental round complexity barrier that scales quadratically with the number of corrupt parties.
We prove that every randomized synchronous Byzantine Agreement protocol in the full-information, strongly adaptive adversary model, secure against $t$ corrupt parties, has worst-case expected round complexity \[ \Omega\!\left(\frac{t^2}{n\log(n+1)}\right). \] This improves upon the seminal $\Omega(\frac{t}{\sqrt{n\log n}})$ bound of [Bar-Joseph, Ben-Or 98]. Our result matches the recent upper bound of $O\left(\min\left\{\frac{t^2\log n}{n},\frac{t}{\log n}\right\}\right)$ of [Dufoulon, Pandurangan 25], up to a $\log^2 n$ factor in the $t\ll n$ regime. Our proof takes inspiration from the recent works of [Etesami, Mahloujifar, Mahmoody 20] and [Haitner, Karidi-Heller 26]. Specifically, we prove a multi-round concentration lemma showing that any transcript event of probability $p$ can be forced with probability one by corrupting $O(\sqrt{n\log(\frac1p)})$ parties in expectation. From there, tools from [Chor, Merritt, Shmoys 89] allow us to lower-bound the probability of the protocol not concluding in $R$ rounds by $\frac{1}{n^{O(R)}}$, using a crash schedule involving at most $R$ parties. The combination of these techniques yields the desired bound.
