Byzantine Fault Tolerance
Byzantine Fault Tolerance

By piotrillo | Short trip into tech | 26 Jan 2020


The problem of the Byzantine generals, also called problem of interactive consistency. This refers to a problem of consistency. It is about the task of making common and precise decisions in a network. The problem can best be described with a metaphor.

Suppose three generals want to conquer a city, but it can happen that one of them is a traitor. The city can only be successfully captured if all generals follow the same strategy, either they attack or they stay on their positions and the siege continues. The generals can only communicate through messengers.

The traitor sends contradictory messages; to a general he sends the command to attack and the others to retreat.

The two loyal generals have no way of controlling the commands of each other generals, because they cannot know who is telling the truth, and who is lying. This way the traitor remains undiscovered and can prevent the conquest of the city. You have therefore devised a different approach, the so-called Byzantine Agreement.

Responsiveness - a consensus-based approach, this algorithm fulfils the following

Conditions:

  • All loyal generals know the same decision in the end, regardless of Actions of the traitors.
  • it must not be possible for a small number of traitors to interfere with the plans of the others to thwart generals.

 

Consensus is reached based on a majority decision. Each general chooses the alternative chosen by most of the generals.

See also the following figure. General C is the defector. He gives conflicting orders, A, the order to attack and B, the order to retreat.

A forwards the message to attack to B and B for retreat to A.

A now knows that one of them has bad intentions, but he cannot verify who did this and what the correct message should be. Suppose, in a network where one node corresponds to a general, it is impossible to make a clear decision if one of them produces false messages.

351665157-83fc4a2c8e9db84cd8a6fa9aef8a5164174f88efb95ce8a302501566704cf273.jpeg

 

In a system that is tolerant of Byzantine error, the number traitors no greater than 1/3 of all generals. The general formula is Let n be the number of generals and t the number of traitors. Then it is valid: There can be clear solution can be achieved if n≥3t+ 1. One solution to this problem is the Signing messages so that it is traceable who the sender is. Faulty transactions can distort communication, so the origin of all transactions must be uniquely identified so that the senders of incorrect transactions can be located and misinformation can be intercepted.

Byzantine agreement is possible if the number of erroneous transactions is less than n/3.

 


piotrillo
piotrillo

it enthusiast


Short trip into tech
Short trip into tech

You will find my thoughts and ideas about new technologies and the world.

Send a $0.01 microtip in crypto to the author, and earn yourself as you read!

20% to author / 80% to me.
We pay the tips from our rewards pool.