A Review of Consensus Protocols

The processes must somehow propose their candidate values, communicate with one another, and decide on a single consensus value.In this post I review four major consensus protocols for solving the consensus problem based on my implementation of them, namely:You can find supporting code for this analysis in this GitHub repository: ConsensusKitBefore getting started let’s recap the three key properties of consensus protocols and take a quick look at relevant terminology for this discussion.Formally a consensus protocol must satisfy the following three properties:TerminationIntegrityAgreementThese requirements are rather straight forward. Any value agreed upon by all correct processes must have been voted by at least one decider.An application or a subsystem that is responsible for persisting decided values and implementing a protocol’s specific data constraints.An application or a subsystem that is responsible for the detection of node failures or crashes.A protocol’s specific threshold requiring at least half of available votes, more when faulty processes are taken into account.A protocol’s specific threshold which ensures that a minimum number of participants (or votes) is met for taking an action.With these definitions in place let’s move on to the implementation and review of each consensus protocol.My main goal has been to implement these four protocols in code to be able to run and evaluate them in a controlled environment. Then the decider picks the most recent message value, possibly validating the value with the archiver, and broadcasts the selected value back to all processes.After broadcasting the selected value the decider waits for a quorum of proposers to acknowledge it, in which case it decides on that value and broadcasts its decision to all processes before terminating.Notice that this simplified implementation doesn’t take failures into account, even though the Chandra–Toueg protocol is fault-resilient.Ben-Or is a decentralized consensus protocol, i.e., it doesn’t assign the decider role to any specific process. Agreement is enforced by guaranteeing that only one proposal can get the votes of a majority of accepters, and validity follows from only allowing input values to be proposed3.The basic Paxos algorithm is briefly presented below:Now let’s look at the code implementation starting with the the proposer role behavior:Obs: Usage of Math.Max in this snippet may seem redundant, but it was actually employed to solve a race condition without resorting to a mutex.You can see that in this case the Process.Propose method was overridden to implement the Paxos protocol proposal numbering logic, and that I’ve used the MessageType.Propose enum member to represent the “prepare” message.After broadcasting its proposal number the process will wait for either MessageType.Ack or MessageType.Nack responses. The act of delivering a proof of work on a block, in order for a process to propose that block to the network, is called “mining”.The algorithm can be briefly described in two sentences as follows4:The purpose of the k-deep confirmation rule is to reduce the chances of a process deciding on an uncertain/volatile data block to a negligible probability.Even though the Nakamoto consensus protocol has a simple form, it requires a reasonable amount of code for implementing the block mining and block chains management logic.