distributed ledger

Byzantine Fault Tolerance - Part 1: The Generals Problem

One of the most common words that you'd come across when you read about distributed systems, ledgers, blockchains etc is Byzantine Fault Tolerance - BFT. For a beginner, this might sound overwhelming and confusing at the same time, since this is associated with yet another word, Consensus.

The need for a Consensus in any distributed system where multiple parties end up keeping all or parts of the full data set is due to the fact that disagreement might arise in which copy of the data is accurate. In today's world where we tend to ignore the intricacies of network delays and latency, it is still a concern to realize that two different copies of the same original data might end up being circulated within a very short difference in time, making it difficult for the participants to decide which originated first, and which to discard.

Thus comes the need for Consensus, in other words, agreement.

Understanding the need for consensus, we need to evaluate how we can come to it. It is comparatively easy in priority based systems, but in a system where all participants are equal, and the data is immutable, i.e., cannot be corrected or modified if gone wrong, it is extremely important to first agree on a system of agreement, or the consensus protocol.

To quickly get into the reality of a lack of consensus, let us take the age old Generals Problem. This problem is best described in the 1970s as a classic example of consensus which can never be attained.

The Generals Problem

Consider the case where we have two generals - Rudolf and Gabriel, who wish to attack an enemy camp. They do not have the war force to attack and win independent of the other, and they are stationed each other across the enemy. To attack the enemy and win, they both have to agree on a time when they both will attack simultaneous from both sides, thereby achieving victory. However, they both have to agree on a definite time.

In order to discuss and finalize on the time of attack, one or both of the generals send a messenger to the other with a proposed time of attack. However, the messenger needs to travel to the other general's camp crossing the enemy base. Thus arises a possibility of capture of the messenger.

Considering the possible outcomes:

  1. The messenger from General Rudolf to General Gabriel with a message
  2. The messenger goes back from General Gabriel to General Rudolf with an acknowledgement

However, the messenger can be caught at any of this travel, be it back or forth, so there is a need for a third acknowledgement from General Rudolf to General Gabriel acknowledging the acknowledgement. This doesn't stop at the third acknowledgement since General Rudolf needs an acknowledgement for this from General Gabriel.

A typical example of The Generals Problem

This will result in an infinite trips across each other with a 50% probability of the messenger being caught in any of this trips. Thus there is never a 100% certainty of the generals agreeing on the time of attack. Without such a certainty, the generals do not attack. The attack hence never happens.

It is generally accepted that the Generals Problem do not have a fool proof solution.

The Two Generals Problem and its impossibility proof was first published  by E. A. Akkoyunlu, K. Ekanadham, and R. V. Huber in 1975 in "Some  Constraints and Trade-offs in the Design of Network Communications"

A further situation of such a problem is best explained as part of the Byzantine Generals Problem, which I will detail in part 2 of this blog post.

0 Comments 0 Comments
0 Comments 0 Comments