Fast asynchronous Byzantine agreement with optimal resilience
Ran Canetti, Tal Rabin · 1993
It is known that, in both asynchronous and synchronous networks, no Byzantine Agreement (BA) protocol for n players exists if d e of the players are faulty (in other words, no BA protocol is d e-resilient). The only known asynchronous (d e \\Gamma 1)-resilient BA protocol runs in expected exponential time, and the best resilience achieved by an asynchronous protocol with polynomial complexity is (d 4 e \\Gamma 1). The question whether there exists an asynchronous (d BA protocol with polynomial complexity remained open.