Задача византийских генералов
Классическая логическая дилемма, описывающая сложность достижения согласия в ненадежной сети.
The Byzantine Generals Problem (BGP) is a logical dilemma formulated by Leslie Lamport, Robert Shostak, and Marshall Pease in 1982. It describes a scenario where several divisions of the Byzantine army are camped outside an enemy city. Each division is led by a general, and all must decide on a common plan: to attack or retreat. To succeed, all honest generals must agree and execute the same plan. However, some generals may be traitors who send conflicting messages to cause failure. BGP illustrates the fundamental challenge of ensuring consistency in decentralized networks where nodes may be faulty or adversarial.
graph LR
Center["Задача византийских генералов"]:::main
Pre_distributed_systems["distributed-systems"]:::pre --> Center
click Pre_distributed_systems "/terms/distributed-systems"
Center --> Child_byzantine_fault_tolerance["byzantine-fault-tolerance"]:::child
click Child_byzantine_fault_tolerance "/terms/byzantine-fault-tolerance"
Rel_consensus_mechanisms["consensus-mechanisms"]:::related -.-> Center
click Rel_consensus_mechanisms "/terms/consensus-mechanisms"
Rel_proof_of_work["proof-of-work"]:::related -.-> Center
click Rel_proof_of_work "/terms/proof-of-work"
Rel_digital_signatures["digital-signatures"]:::related -.-> Center
click Rel_digital_signatures "/terms/digital-signatures"
classDef main fill:#7c3aed,stroke:#8b5cf6,stroke-width:2px,color:white,font-weight:bold,rx:5,ry:5;
classDef pre fill:#0f172a,stroke:#3b82f6,color:#94a3b8,rx:5,ry:5;
classDef child fill:#0f172a,stroke:#10b981,color:#94a3b8,rx:5,ry:5;
classDef related fill:#0f172a,stroke:#8b5cf6,stroke-dasharray: 5 5,color:#94a3b8,rx:5,ry:5;
linkStyle default stroke:#4b5563,stroke-width:2px;
🧒 Простыми словами
🏰 Представьте трех генералов. Им нужно напасть одновременно, чтобы победить. Если нападут только двое — они проиграют. Но один генерал может быть шпионом, который говорит одному 'Нападаем', а другому 'Ждем'. Задача в том, как честным генералам договориться вопреки этой лжи.
🤓 Expert Deep Dive
## Technical Deep Dive: Lamport's Proof
In the 1982 paper, it was shown that with only 3 generals (A, B, C) where one is a traitor (C), consensus is impossible.
### The Failure Scenario
1. General A sends 'Attack' to B and C.
2. General C (traitor) says 'Retreat' to B.
3. General B now sees 'Attack' from A and 'Retreat' from C. He cannot know who is the traitor.
This simple proof necessitates the $3f+1$ rule for non-cryptographic BFT. With Digital Signatures, a general cannot lie about what another general said, which drastically simplifies the solution space.