Byzantine General's Problem [English]


Syndetic Relationships

InterPARES Definition

No definition in earlier IP projects. ITrust definition not yet developed.

Other Definitions

  • Deloitte Insights 2016 (†801 p.15): Computer scientists have long concerned themselves with the problem of maintaining a consistent and accurate set of records in a large and complex computer system where malfunctioning components give conflicting information to different parts of the system, or where hacked components deliberately lie in an attempt to subvert the system. Bitcoin is subject to this problem because the integrity of the distributed ledger must be maintained in an environment where some of the miners may be actively working to subvert the ledger. This problem is called the Byzantine Generals’ Problem as it’s often described in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. · The problem is often formulated along the following lines: ‘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.’ — Leslie Lamppost, Robert Shostak & Marshall Pease, The Byzantine Generals’ Problem
  • Scaling Bitcoin [2017] (†845 s.v. "Byzantine (Generals') Problem"): In fault-tolerant computer systems, and in particular distributed computing systems, Byzantine fault tolerance is the characteristic of a system that tolerates the class of failures known as the Byzantine Generals' Problem. As reliable computer systems must handle malfunctioningcomponents 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. Communicatingonly 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.