Byzantine Agreement Problem in Distributed System

In this tutorial you are going to learn about Byzantine Agreement Problem in Distributed System.

Byzantine Agreement Problem

The Byzantine agreement problem was first defined by Lamport. The solution was also given by Lamport first of all under the situation of processor failure.

According to the concept of Byzantine agreement problem, a source processor is taken to broadcast its initial value to another processor in the system. The source processor is selected randomly and sequential ordering is done to choose a source processor.

For getting the byzantine agreement protocol, it is necessary for all non-faulty processors to be agreed on the same value. In some situations, the source processor may be non-faulty. Then its initial value is not used by other processors.

The objective of the Byzantine problem is to be able to defend against failures, in which components of a system are in arbitrary ways, i.e not just by stopping or crashing but by processing requests incorrectly, corrupting their local state and producing incorrect or inconsistent outputs. The Byzantine failure models real world environments in which computers and networks may behave in unexpected ways due to hardware failures, network congestion and disconnection as well as malicious attacks.

Byzantine General’s Problem

A byzantine fault is an incorrect operation (algorithm) that occurs in a distributed system that can be classified as:

• Omission failure - A failure of not being present such as failing to respond to a request or not receiving a request.
• Execution Failure or lying - A failure due to sending incorrect or inconsistent data, corrupting the local state or responding to requests incorrectly.
• Example:
  1. Round off errors passed from one function to another and then another, etc.
  2. Corrupted system databases where the error is not detected.
  3. A compile error.
  4. An undetected bit flip produces a bad message.
• This is a worse case model since the Byzantine failure fault can generate misleading information causing a maximum of confusion.

The byzantine General’s problem is an illustrative example of byzantine faults:

• A number of different armies want to besiege an enemy city. Success requires agreement on a common plan amongst the disbursed army; communication is only by messages.
  • Compilation: There may be traitors who send out conflicting messages to sow confusion.
  • Challenge: Find an algorithm that ensures the armies come to an agreement and attack at the same time.
• Real World Relationships:
  1. Generals->processors
  2. Traitors->faulty processors or faulty system components(including software)
  3. Messengers ->processor communication/system data bus.

Byzantine General’s Problem Scenario

• Several armies, each under the command of a general, are camped outside a city which they plan to attack.
• One of the generals will issue the order attack or retreat
• One or several of the generals may be traitors. To win the battle all loyal generals must attack at the same time.
• The traitors will attempt to fool the loyal general so that not all of them attack at the same time.
• To stop the traitor’s malicious plan, all generals exchange messages directly with each other.

---

This article on Byzantine Agreement Problem in Distributed System is contributed by Hemalatha P. If you like TheCode11 and would like to contribute, you can also write your article and mail to thecode11info@gmail.com