2021/02/25 by Petr Kuznetsov, Andrei Tonkikh, Kuznetsov, Petr +3 · 4 citations
Computer Science · #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Mobile Agent-Based Network Management #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2102.12825
openalex publication_date 2021/02/25 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
It is a common belief that Byzantine fault-tolerant solutions for consensus\nare significantly slower than their crash fault-tolerant counterparts. Indeed,\nin PBFT, the most widely known Byzantine fault-tolerant consensus protocol, it\ntakes three message delays to decide a value, in contrast with just two in\nPaxos. This motivates the search for fast Byzantine consensus algorithms that\ncan produce decisions after just two message delays \in the common case,≠.g., under the assumption that the current leader is correct and not suspected\nby correct processes. The (optimal) two-step latency comes with the cost of\nlower resilience: fast Byzantine consensus requires more processes to tolerate\nthe same number of faults. In particular, 5f+1 processes were claimed to be\nnecessary to tolerate f Byzantine failures.\n In this paper, we present a fast Byzantine consensus algorithm that relies on\njust 5f-1 processes. Moreover, we show that 5f-1 is the tight lower bound,\ncorrecting a mistake in the earlier work. While the difference of just 2\nprocesses may appear insignificant for large values of f, it can be crucial\nfor systems of a smaller scale. In particular, for f=1, our algorithm\nrequires only 4 processes, which is optimal for any (not necessarily fast)\npartially synchronous Byzantine consensus algorithm.\n