Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary

Valerie King, Jared Saia

We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only $\tilde{O}(\sqrt{n})$ bits, where $n$ is the total number of processor…