Practical Solutions

Solutions

There are well-known practical algorithms that reach consensus in the fail-stop model in asynchronous systems. The most widely used algorithm for fault-tolerant consensus in state machine replication is the Paxos protocolLeslie Lamport. Paxos made simple. pages 51-8, December 2001., which was introduced by Lamport. The protocol deals with $2 f+1$ processes, whereas $f$ fail-stop failures may occur. An alternative to Paxos is the Raft algorithmDiego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In Proceedings of the 2014 USENIX Conference on USENIX Annual Technical Conference, USENIX ATC’14, pages 305-20, Berkeley, CA, USA, 2014. USENIX Association. which achieves consensus via leader election. Raft is equivalent to Paxos in fault-tolerance and performance but consists of a different structure. Both original Paxos and Raft protocols assume that nodes only fail by stopping, whereas Byzantine failures consequently subvert the correctness of these algorithms.

Whereas known algorithms assume a synchronous system (cf. this lesson or were too slow to use in practice (such as Ben-Or’s algorithm in this lesson, Castro and Liskov (1999)Miguel Castro and Barbara Liskov. Practical Byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation, OSDI '99, pages 173-86, Berkeley, CA, USA, 1999. USENIX Association. presented the first practical solution for solving the Byzantine Generals Problem in asynchronous systems. The Practical Byzantine Fault Tolerance $(P B F T)$ algorithm “describes the first state-machine replication protocol that correctly survives Byzantine faults in asynchronous systems”, i.e., it works in asynchronous networks like the Internet, thus it can be used in real systems. The algorithm provides safety and liveness (cf. this definition :Properties_of_consensus_protocol) with an optimal resilience as long as not more than $f<n / 3$ replicas are faulty. The protocol assumes independent node failures, therefore it is potentially vulnerable to Sybil attacks (see this section :Sybil_Attack). After the invention of the PBFT algorithm, different Byzantine Fault Tolerant (BFT) protocols appeared that can be used in practice as a consensus mechanism. Well-known protocols are Tangaroa, a BFT variant of the Raft algorithm, or Tendermint (Christopher N. Copeland et al. (2014)Christopher N. Copeland and Hongxia Zhong. Tangaroa: A Byzantine fault-tolerant raft. Corpus ID: 195177332.2014.).

In 2009, a practical implementation was developed with the invention of Bitcoin by Nakamoto (2008), where the Proof-of-Work (PoW) algorithm provides a mechanism to achieve consensus in the permissionless environment. This was the first approach to solving the consensus problem by using a blockchain. For the first time, the voting power was not linked to the number of electoral votes, but rather to the computational power. The underlying mechanism that allows a system to reach an eventual agreement on the blockchain data structure is widely known as the Nakamoto consensus.