Revisiting Optimal Resilience of Fast Byzantine Consensus

DOI10.1145/3465084.3467924arXiv2102.12825OpenAlexW3186862114MaRDI QIDQ6201962FDOQ6201962

Authors:

Publication date: 26 March 2024

Published in: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: It is a common belief that Byzantine fault-tolerant solutions for consensus are significantly slower than their crash fault-tolerant counterparts. Indeed, in PBFT, the most widely known Byzantine fault-tolerant consensus protocol, it takes three message delays to decide a value, in contrast with just two in Paxos. This motivates the search for fast Byzantine consensus algorithms that can produce decisions after just two message delays emph{in the common case}, e.g., under the assumption that the current leader is correct and not suspected by correct processes. The (optimal) two-step latency comes with the cost of lower resilience: fast Byzantine consensus requires more processes to tolerate the same number of faults. In particular, $5f+1$ processes were claimed to be necessary to tolerate $f$ Byzantine failures. In this paper, we present a fast Byzantine consensus algorithm that relies on just $5f-1$ processes. Moreover, we show that $5f-1$ is the tight lower bound, correcting a mistake in the earlier work. While the difference of just $2$ processes may appear insignificant for large values of $f$, it can be crucial for systems of a smaller scale. In particular, for $f=1$, our algorithm requires only $4$ processes, which is optimal for any (not necessarily fast) partially synchronous Byzantine consensus algorithm.

Full work available at URL: https://arxiv.org/abs/2102.12825

zbMATH Keywords

resiliencecommon-case latencyfast Byzantine consensus

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (1)

• Byzantine consensus is \(\Theta(n^2)\): the Dolev-Reischuk bound is tight even in partial synchrony!

This page was built for publication: Revisiting Optimal Resilience of Fast Byzantine Consensus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201962)