Fast Almost-Surely Terminating Byzantine Agreement.
Cheng Wang · arXiv (Cornell University) · 2015
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 {\cite{abraham2008almost}} by a factor of $O (n)$. When $n > (3 + \varepsilon) t$ with any $\varepsilon > 0$, our protocol completes with expected running time $O (1 / \varepsilon)$, improving the state-of-the-art result of Feldman and Micali {\cite{feldman1988optimal}} (with constant expected running time when $n > 4 t$).