000210619 001__ 210619
000210619 005__ 20190317000235.0
000210619 037__ $$aREP_WORK
000210619 245__ $$aAsynchronous Byzantine Agreement with Optimal Resilience and Linear Complexity
000210619 269__ $$a2015
000210619 260__ $$c2015
000210619 336__ $$aReports
000210619 520__ $$aGiven 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$).
000210619 700__ $$0248224$$g233202$$aWang, Cheng
000210619 8564_ $$uhttps://infoscience.epfl.ch/record/210619/files/main.pdf$$zn/a$$s256906$$yn/a
000210619 909C0 $$xU10407$$0252114$$pDCL
000210619 909CO $$ooai:infoscience.tind.io:210619$$qGLOBAL_SET$$pIC$$preport
000210619 917Z8 $$x233202
000210619 917Z8 $$x233202
000210619 917Z8 $$x233202
000210619 937__ $$aEPFL-REPORT-210619
000210619 973__ $$aEPFL
000210619 980__ $$aREPORT