Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

byzantine
bgp
blockchain

What is the Byzantine Generals' problem?

Ahsan Amin

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

What is the Byzantine Generals' problem?

The Byzantine Generals' problem refers to the game theory problem. A group of generals attacks a fortress; every general has an army and surrounds a fort from one side. Every general has a preference about whether to attack or retreat. It has to be a coordinated attack or retreat to incur minimum losses. Thus, a consensus is held, and the majority decision is implemented. This consensus is formed after following the following steps:

  1. Every general sends their own choice to all other generals.
  2. After receiving the choice of all generals, every general calculates the votes in favor of attacking and retreating.
  3. If the majority is in favor of retreat, then they retreat; otherwise, they attack.

Suppose there is a traitor general who sends a retreat message to half generals and an attack message to the other half generals. Then half of the generals may end up attacking while the other half will retreat, causing the army to lose.

The following slides show all the scenarios of a successful attack, a successful retreat, and an unsuccessful attack.

A successful attack
1 of 3

Application

  • Blockchain: In blockchains, we've got a network of nodes (generals), and they have to decide whether to add a block to their journal or not. All the nodes must make the same decision (either to add the block or not) to maintain a constant state of the blockchain across all the nodes. Otherwise, every node will have a different view of the blockchain, making it hard to maintain the network.
  • Distributed systems: In data centers, we have a lot of servers to handle user requests. All these servers have their data; if a user request results in a change in data, then all the servers need to update their data(to keep the data consistent across all the servers). If some servers(generals) fail or send the wrong information at this point, this may bring down the whole system.

RELATED TAGS

byzantine
bgp
blockchain

CONTRIBUTOR

Ahsan Amin
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring