Consensus With at most m Byzantine Faults

Byzantine Faults: In simple terms, a Byzantine Fault is where some nodes start behaving maliciously or abnormally. Here problem is that any such node may send two different value to two different nodes and if so happen then all our previous methods won’t work. Because previously we are sure that if a node sends a value then it will send the same value to every node. 

  State of Network:

• Reliable communication medium
• Synchronous system
• Fully connected
• The receiver always knows the identity of the sender of a message
• S is the set of all the nodes.
• The node who initiates the agreement protocol is the commander
• The value suggested by the commander is the order
• The other nodes, to whom the commander sends the order, are his lieutenants.
• OM stands for Oral Message and this term is just to show that one node can tell two different values to two different nodes.

  Steps:

• We will show here a recursive algorithm called Lamport-Shostak-Pease Algorithm to solve the Byzantine General Problem.
• Base Case- OM(0,S) :
  • The commander i sends the proposed value v to every lieutenant j in S – {i}
  • Each lieutenant j accepts the value v from i
• Recursive Case- OM(m,S):
  • The commander i sends a value v to every lieutenant j ∈ S – {i}.
  • Let vj be the value lieutenant j receives from the commander i, ( 0 if receives no value).
  • Lieutenant j now initiates OM(m-1, S – {i}) with value vj, as a commander. At the end of each of these recursive executions, every loyal lieutenant j ∈ S – {i} has agreed on a set of pairs (k,vk), one for each k ∈ S – {i}.
  • After Step 3 has been completed by all lieutenants, each lieutenant j collects the pairs it received in Step 3 (its own pair containing the original value from its commander and the other pairs containing the values returned by its own lieutenants by the recursive invocation of OM(m,S-{i}) )
  • The each lieutenant j agrees on the value v = majority ( { (k,vk) | k ∈ S -{i} } ) that is in the majority of those pairs.

Here, 

• All the solutions discussed till now are possible when the system is synchronous, completely connected and nodes know the identity of each other.
• In the Byzantine Faults case, no solution is possible if n < (3m + 1).
• In the asynchronous model, the consensus is impossible to achieve even with a single crash failure.
• Consensus is impossible to achieve even with a single link failure, even in the synchronous model.

There are some more Consensus Algorithms for Permissioned Environments like RAFT, PAXOS. Apart from the above discussion, there are some more Consensus Algorithms that are used in Permissionless Environment, like Proof of Work: It is used in Bitcoin.

Consensus is a general agreement on a decision made by the majority of those involved. For example, the problem may be as simple as friends trying to decide which restaurant has multiple options to choose from or complex as decisions on distributed systems.