Lamport's Byzantine Generals algorithm in Python
Imagine a group of generals of the Byzantine army camped with their troops around an enemy city. The generals must agree upon a common battle plan: either attack or retreat. However, some of them may be traitors! The non-traitor generals succeed only if all of them choose the same action — either everyone attacks or everyone retreats; if even one non-traitor general does something different, the battle is lost.
In their seminal paper The Byzantine Generals Problem Lamport, Shostak and Pease pose this problem with the analogue of the Byzantine generals, and give solutions using distributed algorithms. Their abstract reads:
Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system. This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement. It is shown that, using only oral messages, this problem is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals. With unforgeable written messages, the problem is solvable for any number of generals and possible traitors. Applications of the solutions to reliable computer systems are then discussed.
The problem asks: how can distributed processes reach agreement when a subset of them — up to $M$ in a total of $N$ nodes — might behave arbitrarily, lying, omitting, or forging messages? Failures of this kind are called Byzantine because, like traitorous generals, they do not merely crash; they actively try to mislead the rest of the system.
