From Traditional Fault Tolerance to Blockchain

9Consensus Algorithms for Blockchain

Distributed consensus is the most fundamental issue in distributed computing. There has been a strong interest on distributed consensus since early 1980s [31]. Milestones in this line of research are many. We can easily name of few: the logical timestamp concept proposed by Lamport [18], the Byzantine generals problem and the earliest algorithms also proposed by Lamport [21], the impossibility result for asynchronous distributed systems by Fischer, Lynch, and Paterson [11], the group communication systems by Birman [6], Moser, and Melliar-Smith et al. [23], the practical Byzantine fault tolerance algorithm (PBFT) by Castro and Liskov [7], and the Paxos-family of algorithms by Lamport [19, 20].

To remove trivial solutions to the distributed consensus problem, such as everyone always decided on a particular value, it requires that the value chosen by a member must have been proposed by someone in the system. If there is only a single member that always proposes some value, then the solution to the distributed consensus problem is also trivial. However, such assumption is obviously not fault tolerant, i.e., if that member fails, the system stops operating. Hence, at least a subset of the members must share the responsibility to propose values dynamically. Once we allow more than one member to propose, we are risking of different members in the system choose values proposed by different ones. Hence, the distributed consensus is a complex problem. ...