Classification

The consensus algorithms can be classified into two broad categories:

• Traditional—voting-based consensus
• Lottery-based—Nakamoto and post-Nakamoto consensus

Traditional voting-based consensus has been researched in distributed systems for many decades. Many fundamental results and a lot of ground-breaking work have already been produced in this space. Algorithms like Paxos and PBFT are prime examples of such types of algorithms. Traditional consensus can also be called fault-tolerant distributed consensus. In other words, this is a class of consensus algorithms that existed before Bitcoin and has been part of distributed system research for almost three decades.

Lottery-based or Nakamoto-type consensus was first introduced with Bitcoin. This class can also be simply called blockchain consensus.

The fundamental requirements of consensus algorithms boil down to safety and liveness conditions. A consensus algorithm must be able to satisfy the safety and liveness properties. Safety is usually based on some safety requirements of the algorithms, such as agreement, validity, and integrity. Liveness means that the protocol can make progress even if the network conditions are not ideal.

Now we'll define these terms separately:

Safety: This requirement generally means that nothing bad happens. There are usually three properties within this class of requirements, which are listed as follows:

• Agreement. The agreement property requires that no two processes decide on different values.
• Validity. Validity states that if a process has decided a value, that value must have been proposed by a process. In other words, the decided value is always proposed by an honest process and has not been created out of thin air.
• Integrity. A process must decide only once.

Liveness: This requirement generally means that something good eventually happens.

• Termination. This liveness property states that each honest node must eventually decide on a value.

With this, we have covered the classification and requirements of consensus algorithms. In the next section, we'll introduce various consensus algorithms, which we can evaluate using the consensus models covered in this section.