The main idea behind this algorithm is: There is a commander and N lieutenants. The commander initiates the process and sends an initial message to all the lieutenants in the closed network. Later, each lieutenant forwards the value received from the commander to the other lieutenants except the sender. So at the end of the rounds, all the lieutenants must be having N-1 values, except the offline lieutenants. In the end, they will apply the majority voting principle and achieves the consensus. This is one of the first algorithms for Byzantine Generals’ Problem.
Base Condition for Commander
Pulse-1 is the initial pulse where the commander sends the message to all the Lieutenants. Broadcast (N, t=0), where N is the number of processes and t is the algorithm parameter, denotes the individual rounds. The Commander decides his own value, and in this case, the possible values are {retreat, attack}. In this example, N = 3 has three different lieutenants and is trying to reach a consensus.
Base Condition for Lieutenant
Each lieutenant receives the message from the commander and checks whether it is a pulse-1 message or not. If it is a pulse-1 message, and the sender is the commander, accept it; otherwise, wait for a pulse-1 message. Suppose a pulse-1 message is received then broadcast this message to all other processes in the network.
General Condition for Lieutenant
All the lieutenants broadcast their values to the other lieutenants except the senders. At the end of the rounds, all the lieutenants must be having N-1 values, except the offline lieutenants. In the end, they will apply the majority voting principle and achieves the consensus.
In this agreement Protocol, after N rounds, each process must be having the N values; this is because the system is synchronous and having a reliable communication medium. Once they have, N values can apply the majority voting principle and achieve the consensus. However, to achieve consensus, the system should satisfy the below condition.
- The system must have a minimum of three lieutenants (N =3) and a commander. So, out of N number of processes (lieutenants), maximum of F number of the processes can be faulty, and F + 1 number of processes must be non-faulty such that N = 2*F + 1.
- The system should be fully connected, and the receivers always know the identity of the senders.
- The system should be synchronous and having a reliable communication medium.
References
- NPTEL lecture series on Blockchains Architecture, Design and Use Cases by Prof. Sandip Chakraborty, IIT Kharagpur.
929 total views, 1 views today
