Wprowadzenie
Problem Bizantyjskich Generałów to klasyczne zadanie w informatyce sformułowane w 1982 roku przez Leslie Lamporta, Roberta Shostaka i Marshalla Pease’a. Opisuje ono trudności w osiągnięciu porozumienia w systemie rozproszonym, w którym część uczestników może zdradzać lub wysyłać sprzeczne informacje.
Opis problemu
Kilku generałów oblega wrogie miasto. Muszą uzgodnić wspólny plan: wszyscy mają zaatakować lub wszyscy się wycofać. Generałowie komunikują się tylko przez posłańców, ale wśród nich mogą być zdrajcy, którzy celowo wysyłają fałszywe wiadomości.
Główne wyzwania
- Jak osiągnąć konsensus, gdy część generałów kłamie?
- Jak wykryć zdrajców?
- Jak zapewnić, że lojalni generałowie podejmą tę samą decyzję?
Rozwiązanie
Lamport udowodnił, że przy użyciu ustnej wiadomości (niepodpisanej) konsensus jest możliwy tylko jeśli zdrajców jest mniej niż ⅓ wszystkich generałów.
Dzięki wprowadzeniu podpisów cyfrowych (kryptografii) można osiągnąć konsensus nawet przy większej liczbie zdrajców.
Znaczenie dla dzisiejszych technologii
- Podstawa algorytmów Byzantine Fault Tolerance (BFT)
- Fundament wszystkich blockchainów (Bitcoin, Ethereum, Solana itp.)
- Kluczowe w systemach rozproszonych, federated learning i decentralizowanym AI
- Bezpośrednio związane z mechanizmami konsensusu w kryptowalutach
Aktualny status (2026)
Problem Bizantyjskich Generałów pozostaje jednym z najważniejszych teoretycznych fundamentów współczesnych systemów rozproszonych. Rozwiązania BFT są szeroko stosowane w blockchainach, a nowe algorytmy (np. HotStuff, DAG-based BFT) ciągle rozwijają to pole, umożliwiając coraz szybsze i bezpieczniejsze sieci.
Powiązane pojęcia
Byzantine Fault Tolerance • Consensus Algorithms • Lamport’s Problem • Distributed Systems • PBFT • Blockchain Security