Given a system with processes, where is the tolerated number of faulty ones, we present a fast asynchronous Byzantine agreement protocol that can reach agreement in expected running time. This improves the expected running time of Abraham, Dolev, and Halpern [PODC 2008]. Furthermore, if for any , our protocol can reach agreement in expected running time. This improves the result of Feldman and Micali [STOC 1988] (with constant expected running time when ).
François Maréchal, Jonas Schnidrig, Cédric Terrier
Florian Frédéric Vincent Breider, Myriam Borgatta