Consensus Algorithm – The decision-making ability of machines in a distributed network

The word consensus means “general agreement”; In a structured human society, the agreement is based on either pre-defined law, governance-model or based on the collective decisions agreed upon by the majority. Let's says, if an individual would like to take a decision on the scale where a group of individuals are impacted then a hypothetical group is being formed and every individual’s decision is considered; also a master or head is assigned to take the final decision, it could be based on the voting. The decision gets either approval or rejection based on the majority of votes.

In an unstructured society, the agreement could be based on power or position which is a different form of consensus.

As human society has transformed over the years, the consensus problem is divided by forming two groups i.e., democratic or autocratic. Both models have their own advantages and disadvantages.

Three famous philosophers - Socrates, Plato, and Aristotle think very differently about the democratic system. Socrates tried to defend the democratic system even as it condemned him to death. Plato did not distrust democracy whereas, Aristotle feared the democracy could lead to mob rule.

The problem of consensus is not only with the human but also with the machines. In a distributed computing models (like blockchain) where multiple nodes are involved and a decision needs to be taken like adding a new block into the blockchain or synchronize the clock based on the geographical region or load balance the traffic poses a fundamental problem. This requires coordinating processes to reach a consensus or agree on some data value that is needed during computation.

The following diagram shows the architecture of blockchain. The consensus layer is using an algorithm to add or discard a new block into the blockchain and mainly responsible for the integrity of the system.

Currently, the following available algorithms for the consensus network has either one of the issues like energy consumption, scalability, immutable and transparent data storage –

• Proof-of-Work (PoW)
• Proof-of-Stake
• Delegated Proof of Stake
• Proof of Elapsed Time
• Byzantine Fault Tolerance

Let us take an example of Byzantine Fault Tolerance (BFT) to understand this problem in detail. The problem was explained aptly in a paper by Leslie Lamport, Robert Shostak, and Marshall Pease at Microsoft Research in 1982:

“Imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching an agreement. The generals must decide on when to attack the city, but they need a strong majority of their army to attack at the same time. The generals must have an algorithm to guarantee that (a) all loyal generals decide upon the same plan of action, and (b) a small number of traitors cannot cause the loyal generals to adopt a bad plan. The loyal generals will all do what the algorithm says they should, but the traitors may do anything they wish. The algorithm must guarantee condition (a) regardless of what the traitors do. The loyal generals should not only reach agreement but should agree upon a reasonable plan.”

Byzantine fault tolerance can be achieved if the majority of 2/3 correctly working nodes in the network reach an agreement on their values. There can be a default vote value given to missing messages.

The main problem with the Byzantine fault tolerance (BFT) is that on failure to return a result or if a responded respond with an incorrect result or deliberately misleading result is provided by the majority of the nodes then it could lead to the different result.

Still, the search for a consensus algorithm that is energy-efficient, respond to the failures of nodes and scale when the number of nodes grows in billions is on. It would be interesting to see if any AI-based model could solve this issue.

Thoughts?