ビザンチン将軍問題 悪意や障害の中での分散合意

「ビザンチン将軍問題」は中央システムがなく、参加者の中に故障したコンピュータや悪意を持った個人が含まれている状態で、全体で正しい合意に到達できるかが焦点にある問題だ。1982年にコンピュータ科学者であるレスリー・ランポートらによって考案されたものである。

ビザンチン将軍問題  悪意や障害の中での分散合意

「ビザンチン将軍問題」は中央システムがなく、参加者の中に故障したコンピュータや悪意を持った個人が含まれている状態で、全体で正しい合意に到達できるかが焦点にある問題だ。1982年にコンピュータ科学者であるレスリー・ランポートらによって考案されたものである。

このジレンマは、各将軍がそれぞれの軍隊を持っており、各グループは攻撃しようとしている都市の周辺の異なる場所に位置していると仮定している。将軍たちは、攻撃するか退却するかについて合意する必要があります。この問題においては、すべての武将が合意に達している限り、攻撃するか退却するかは重要ではない。

したがって、次のような要件を考えることができる。

  • 各将軍は決定しなければならない:攻撃か退却か(イエスかノーか)。
  • 決定後は変更できない。
  • すべての将軍は同じ決定に同意し、同期して実行しなければならない。

将軍は、宅配便で転送されたメッセージを介してしか他の将軍と通信できない。その結果、ビザンチン将軍問題の中心的な課題は、メッセージが何らかの形で遅れたり、破壊されたり、紛失したりする可能性があるということである。

さらに、メッセージが正常に配信されたとしても、1人以上の将軍が(理由は何であれ)悪意を持って行動し、他の将軍を混乱させるために不正なメッセージを送信し、完全な失敗につながる可能性がある。

レスリー・ランポートの1982年の論文に掲載された図。司令官と中尉2人の構成だが、一人でも反逆者が混ざるだけで、正しい合意に到達できなくなる。Source: Leslie Lamport et al."The Byzantine Generals Problem".

コンピューターネットワークのなかのビザンチン将軍問題

この比喩は、多くのコンピュータネットワークを悩ませている問題を説明している。分散コンピューティング環境、つまり複数のユーザー、アプリケーション、サーバー、または他のタイプのノードが環境を構成している環境(ブロックチェーンのようなもの)では、不正な行為者や信頼性の低い行為者が環境を崩壊させる危険性がある。サーバークラスタ内の一部のサーバーが、他のサーバーへのデータの一貫した受け渡しに失敗すると、サーバークラスタはうまく機能しない。コンピュータネットワーク上のデバイスが、情報を交換する際に使用する共通のネットワーキングプロトコルに合意していない場合、コンピュータネットワークは失敗する。

信頼性を確保するためには、分散コンピューティング環境は、ビザンチン障害耐性(BFT)として知られているものを提供することで、ビザンチン将軍の問題を解決するように設計されなければならない。

ビザンチン障害耐性(Byzantine Fault Tolerance: BFT)

ビザンチン障害耐性(BFT)とは、ビザンチン将軍問題から派生した障害に抵抗できるシステムの特性のことを示している。つまり、BFTシステムは、一部のノードが故障したり、悪意を持って行動したりしても、動作を継続できる。

ビザンチン将軍問題に対する解決策は1つ以上あり、それゆえBFTシステムを構築する方法も複数ある。同様に、ブロックチェーンがビザンチン障害耐性を達成するための異なるアプローチがあり、これがいわゆるコンセンサスアルゴリズムにつながる。

ほとんどの従来の分散コンピューティング環境には、ビザンチン障害が発生した場合に過ちを正すのに役立つ中央の設定データベースや権限がある。しかし、ブロックチェーン上には、定義上、中央システムは存在しません。コミュニティのコンセンサスだけに基づいて取引を正当化するブロックチェーンの能力が、ブロックチェーンをこれほど強力なものにしている。

このコミュニティ・コンセンサスへの依存度の高さが、ビザンチン・フォールトをブロックチェーンにとって特に重要な課題としている。コミュニティの一部のメンバーが、トランザクションに関する一貫性のない情報を他のメンバーに発信してしまうと、ブロックチェーンの信頼性が崩れてしまい、それを修正するために踏み込んでくれる権威がいなくなってしまう。つまり、ブロックチェーンに参加している全員に絶対的な信頼を置くことができない限り(ほとんどの状況ではできません)、一部のメンバーが不正確な情報や誤解を招く情報、悪意のある取引情報を配信した場合に発生する可能性のあるビザンチン将軍問題から守る方法が必要になるということだ。

参考文献

Leslie Lamport et al."The Byzantine Generals Problem". ACM Transactions on Programming Languages and Systems | July 1982, pp. 382-401

Photo by British Library on Unsplash

Read more

AI時代のエッジ戦略 - Fastly プロダクト責任者コンプトンが展望を語る

AI時代のエッジ戦略 - Fastly プロダクト責任者コンプトンが展望を語る

Fastlyは、LLMのAPI応答をキャッシュすることで、コスト削減と高速化を実現する「Fastly AI Accelerator」の提供を開始した。キップ・コンプトン最高プロダクト責任者(CPO)は、類似した質問への応答を再利用し、効率的な処理を可能にすると説明した。さらに、コンプトンは、エッジコンピューティングの利点を活かしたパーソナライズや、エッジにおけるGPUの経済性、セキュリティへの取り組みなど、FastlyのAI戦略について語った。

By 吉田拓史
宮崎市が実践するゼロトラスト:Google Cloud 採用で災害対応を強化し、市民サービス向上へ

宮崎市が実践するゼロトラスト:Google Cloud 採用で災害対応を強化し、市民サービス向上へ

Google Cloudは10月8日、「自治体におけるゼロトラスト セキュリティ 実現に向けて」と題した記者説明会を開催し、自治体向けにゼロトラストセキュリティ導入を支援するプログラムを発表した。宮崎市の事例では、Google WorkspaceやChrome Enterprise Premiumなどを導入し、災害時の情報共有の効率化などに成功したようだ。

By 吉田拓史
​​イオンリテール、Cloud Runでデータ分析基盤内製化 - 顧客LTV向上と従業員主導の分析体制へ

​​イオンリテール、Cloud Runでデータ分析基盤内製化 - 顧客LTV向上と従業員主導の分析体制へ

Google Cloudが9月25日に開催した記者説明会では、イオンリテール株式会社がCloud Runを活用し顧客生涯価値(LTV)向上を目指したデータ分析基盤を内製化した事例を紹介。従業員1,000人以上がデータ分析を行う体制を目指し、BIツールによる販促効果分析、生成AIによる会話分析、リテールメディア活用などの取り組みを進めている。

By 吉田拓史
Geminiが切り拓くAIエージェントの新時代:Google Cloud Next Tokyo '24, VPカルダー氏インタビュー

Geminiが切り拓くAIエージェントの新時代:Google Cloud Next Tokyo '24, VPカルダー氏インタビュー

Google Cloudは、年次イベント「Google Cloud Next Tokyo '24」で、大規模言語モデル「Gemini」を活用したAIエージェントの取り組みを多数発表した。Geminiは、コーディング支援、データ分析、アプリケーション開発など、様々な分野で活用され、業務効率化や新たな価値創出に貢献することが期待されている。

By 吉田拓史