Distributed computationにおけるビザンチン障害

Overcoming the “Impossible” Distributed Consensus

Mathematicians identifies distributed computing as a domain fraught with structual challenges, particularly due to asynchrony—the lack of a common clock among participants. In this environment, achieving “consensus” (where all processors agree on a single value, despite malicious “Byzantine” failures) is mathematically impossible for deterministic algorithms

「不可能」と思われた分散型コンセンサスの克服　
分散コンピューティングは、特に非同期性（参加者間で共通のクロックが存在しない）のために、深刻な課題を抱えた領域である。このような環境において、悪意のある「ビザンチン」障害にもかかわらず、すべてのプロセッサが単一の値に合意する「コンセンサス」を達成することは、決定論的アルゴリズムでは数学的に不可能である。ビットコインではビザンチン問題を解決するための確率的合意（Probabilistic Consensus）モデルを採用している。

ビザンチン障害が発生しても、システム全体が正しく動き続ける性質を BFT (Byzantine Fault Tolerance) と呼びます。数学的には、裏切り者が全ノードの 1/3未満 であれば、正しい合意ができることが証明されています。つまり、総数 n に対して故障数が f の場合、 n ≧ 3f + 1 の関係が必要です。