Loading...
report
Asynchronous Byzantine Agreement with Optimal Resilience and Linear Complexity
2015
Given a system with $n > 3t + 1$ processes, where $t$ is the tolerated number of faulty ones, we present a fast asynchronous Byzantine agreement protocol that can reach agreement in $O(t)$ expected running time. This improves the $O(n^2)$ expected running time of Abraham, Dolev, and Halpern [PODC 2008]. Furthermore, if $n = (3 + \varepsilon) t$ for any $\varepsilon > 0$, our protocol can reach agreement in $O (1 / \varepsilon)$ expected running time. This improves the result of Feldman and Micali [STOC 1988] (with constant expected running time when $n > 4 t$).
Loading...
Name
main.pdf
Access type
openaccess
Size
250.88 KB
Format
Adobe PDF
Checksum (MD5)
bbd34d597692a796cc1029aca816c66d