By reviewing the paper “Impossibility of Distributed Consensus with One Faulty Process” [1], we went through the process of proving that no distributed consensus can satisfy both safety and liveness in an asynchronous network setting. That also means there is no ‘perfect’ distributed consensus, so we have to choose what to compromise between safety and liveness for the practical implementation.
- Safety All non-faulty nodes can agree on the sequence of requests, like a centralized implementation that executes operations atomically one at a time. i.e., if there has been a consensus between all non-faulty nodes, every node should be able to access the identical value.
- Liveness Clients who cast their request must eventually receive replies. It implies that the distributed system eventually achieves consensus or in other words, agrees on the same state.
BFT Systems
Partition tolerant consensus algorithms are as far as we’re going to go in terms of fault-tolerant algorithms that maintain single-copy consistency. There is a further class of fault tolerant algorithms: algorithms that tolerate arbitrary (Byzantine) faults;
these include nodes that fail by acting maliciously. Such algorithms are rarely used in commercial systems, because they are more expensive to run and more complicated to implement.
When it comes to partition tolerant consensus algorithms, the most well-known algorithm is the Paxos algorithm. It is, however, notoriously difficult to implement and explain, so I will focus on Raft, an algorithm designed to be easier to teach and implement.
Although people got so hung up in the pseudo-Greek names that they found the paper hard to understand, the algorithm itself is very simple. So, I cornered a couple of people at the conference and explained the algorithm to them orally, with no paper. When I got home, I wrote down the explanation as a short note, which I later revised based on comments from Fred Schneider and Butler Lampson. The current version is 13 pages long, and contains no formula more complicated than n1 > n2 http://lamport.azurewebsites.net/pubs/pubs.html#paxos-simple
BFT algorithms proliferated through approximately 3 decades and have had many applications in diverse settings such as in aviation, space and nuclear power plants industries.
https://captainaltcoin.com/what-is-practical-byzantine-fault-tolerance-pbft/
For example, in aeronautics, that correct functioning of an airplane depends on the correct transmission of information relayed by the many thousands of independent sensors, hence the system must be BFT to be able to continue its flying course even in the presence of many sensors failing to correctly communicate, thus avoiding systemic failure which could lead to an airplane crash
https://elaineou.com/2017/02/12/byzantine-fault-tolerant-airplanes/
https://notes.eatonphil.com/2024-02-08-an-intuition-for-distributed-consensus-in-oltp-systems.html