BGP

BGP is a classic thought experiment in the area of reliability and fault tolerance in distributed systems. The problem illustrates the challenges of achieving reliable consensus when some components are unreliable or behaving unexpectedly.

Imagine a group of generals of the Byzantine Empire of Rome, in around 300 CE, camped with their troops around an enemy city. The generals can use only a messenger to communicate with each other. To win the battle, all the generals must agree upon a common plan of action. Some of the generals could be traitors who can confuse the loyal generals.

The loyal generals need a way to reliably agree upon a coordinated plan of action, even in the presence of these traitorous generals spreading false information. This is a non-trivial problem because of the following reasons:

• The generals can only communicate through a messenger, which can fail or be intercepted.
• Some fraction of the generals may be traitors who will deliberately try...