Asynchronous Byzantine Agreement with Optimal Resilience and Linear Complexity

2015/07/22 by Wang, Cheng
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · doi:10.48550/arxiv.1507.06165

Abstract

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²) expected running time of Abraham, Dolev, and Halpern [PODC 2008]. Furthermore, if n = (3 + ε) t for any ε > 0, our protocol can reach agreement in O (1 / ε) expected running time. This improves the result of Feldman and Micali [STOC 1988] (with constant expected running time when n > 4 t).

Related

• An Almost-Surely Terminating Polynomial Protocol for Asynchronous Byzantine Agreement with Optimal Resilience
• Validated Asynchronous Byzantine Agreement with Optimal Resilience and Asymptotically Optimal Time and Word Communication
• From Few to Many Faults: Adaptive Byzantine Agreement with Optimal Communication
• The Contest Between Simplicity and Efficiency in Asynchronous Byzantine\n Agreement
• Byzantine Agreement in Polynomial Time with Near-Optimal Resilience