An Almost-Surely Terminating Byzantine Agreement with Optimal Resilience and Linear Complexity

We present a new asynchronous Byzantine agreement protocol with almost-sure termination, i.e. all correct processes terminate with probability one. In a system with n = 3t+ 1 processes, where t is the tolerated number of faulty ones, our protocol has linear expected running time, improving on the time complexity of the state-of-the-art protocol of Abraham, Dolev, and Halpern [1] by a factor of O(n). When n> (3 + ε)t with any ε> 0, our protocol completes with expected running time O(1/ε), improving the state-of-the-art result of Feldman and Micali [6] (with constant expected running time when n> 4t)