Summary

Chapter recap

We’ve shown that the solvability of consensus problems in the presence of faults highly depends on the assumptions of the system model. Consensus and Byzantine agreement in the presence of $f$ faulty processes can be reached deterministically in synchronous models in $f+1$ rounds, whereas $n>f$ processes are required in the fail-stop model and $n \geq 3 f+1$ in the Byzantine case without authentication. Authenticated messages improve this result to $f<n$ Byzantine failures.

In asynchronous systems, no deterministic consensus protocol can tolerate even one single crash failure, as stated by the FLP impossibility result. In order to circumvent the FLP result, different extensions to the base model are possible, such as randomized protocols, partial synchrony, failure detectors, or wormholes. However, approaches like randomization, partial synchrony, or failure detectors require $n \geq 3 f+1$ processes for achieving consensus in the asynchronous Byzantine message-passing model. Hybrid models, i.e., wormholes, improve this bound to $n \geq 2 f+1$ processes, whereby these models need to rely on the synchrony of a subsystem.

Considering asynchronous systems with Byzantine failures, early solutions have been propagated but were considered impractical for practical implementations. The first practical solution for this problem was presented by Castro and Liskov (1999) with the PBFT algorithm. This approach assumes $f<n / 3$ faulty processes, thus it’s prone to Sybil attacks. Subsequently, Nakamoto (2008) proposed a Proof-of-Work based consensus algorithm, which allows reaching an eventual agreement in a fully trustless environment.