Strap in as we embark on a thrilling journey into the complex and captivating world of the Byzantine Generals Problem! OK… so maybe not thrilling, but it’s at least mildly interesting. While sounding simple at first, it quickly devolves into a riddle wrapped in an enigma, tucked inside a computer science paradox.
What Is The Byzantine Generals Problem?
The Byzantine Generals Problem is a fundamental issue that arises when you have multiple parties that are communicating and must reach consensus despite potential systems failures, deception or betrayal. The text book analogy that’s used to illustrate this problem involves the Byzantine army invading a city.
How do you make sure that multiple entities, which are separated by distance, are in absolute full agreement before an action is taken?Mike Maloney
The Byzantine army, along with the Byzantine navy, was the main armed forces for the Eastern roman army between 395-1453. Now, imagine that this group of armed men are attacking an enemy city and have totally surrounded the cities walls.
To make things super simple, there’s just one General and two Lieutenants. They lead three separate armies of men around the perimeter and need to communicate with each other in order to pull off a successful attack on the city.
Our problem is, how do they communicate with each other and all agree on a course of action? This agreement is called consensus.
Deception In The Ranks
Like many intractable problems it seems simple on the surface. The general just needs to send messengers to the two Lieutenants that says “attack at noon” and the problems solved! But what if one of the Lieutenants is a traitor?
As you can see, our traitorous Lieutenant receives the correct “attack” message, but then reports to the other loyal Lieutenant that they actually received “hold”. This creates confusion and when noon comes, only the Generals men actually attack resulting in a lost battle.
But it gets worse.