Задача візантійських генералів
Класична логічна дилема, що описує складність досягнення згоди в ненадійній мережі.
Задача візантійських генералів — це уявний експеримент, що ілюструє виклики досягнення консенсусу в децентралізованих системах. Група генералів повинна домовитися про спільний план нападу, але деякі з них можуть бути зрадниками. Для успіху всі чесні генерали мають прийняти однакове рішення, попри дезінформацію від зрадників.
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
Лемпорт довів, що при використанні лише усних повідомлень рішення неможливе, якщо кількість зрадників становить 1/3 або більше від загальної кількості. Біткоїн вирішив цю задачу за допомогою Proof-of-Work, додавши економічну вартість до кожної 'спроби' зради.