2022/02/18 by Shir Cohen, Cohen, Shir, Idit Keidar +3
Computer Science · #Cryptography and Data Security #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Privacy-Preserving Technologies in Data #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2202.09123
openalex publication_date 2022/02/18 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
Byzantine Agreement is a key component in many distributed systems. While Dolev and Reischuk have proven a long time ago that quadratic communication complexity is necessary for worst-case runs, the question of what can be done in practically common runs with fewer failures remained open. In this paper we present the first Byzantine Broadcast algorithm with O(n(f+1)) communication complexity, where 0≤ f≤ t is the actual number of process failures in a run. And for BA with strong unanimity, we present the first optimal-resilience algorithm that has linear communication complexity in the failure-free case and a quadratic cost otherwise.