The Byzantine Generals Problem
Understand consensus when nodes can exhibit arbitrary behavior.
We'll cover the following...
At this point, we know that if a network can lose messages, the consensus is not guaranteed; or if a network can arbitrarily delay messages or nodes have arbitrarily long pauses, then a single crash failure can hinder achieving consensus. In this lesson, we’ll see a scenario where we assume that the network is non-faulty, but nodes can have serious (and hard to detect) Byzantine failures. We want to see if consensus is possible when Byzantine failures are possible in a non-faulty network.
Problem setup
The Byzantine general’s problem has multiple generals (three shown in the picture below) who want to generate consensus about attacking a city. The challenge here is that some number of generals are traitors who can act maliciously (for example conveying different things to different generals). The goal is that non-Byzatine general reach a common decision. As in the two-general problem, the messages are conveyed by messengers. Contrary to the two-general setup, we assume messages get delivered reliably and are not lost.
Let's understand the challenges using the following two scenarios. In the first scenario, let's assume that General 2 is a traitor. General 1 sends attack messages to all. General 2 lies to General 3 that General 1 said to retreat. Now General 3 has two messages, saying conflicting things. To see why it is not easy for General 3 to decide which General is a traitor, let's see the second scenario, which from General 3's perspective, is indistinguishable from the first scenario. Here, General 1 is the traitor. So General 3 can't decide whether General 1 is the traitor or General 2. This makes us think that consensus is probably impossible in this specific case.
