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

「ビザンチン将軍問題」は中央システムがなく、参加者の中に故障したコンピュータや悪意を持った個人が含まれている状態で、全体で正しい合意に到達できるかが焦点にある問題だ。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

米国のEV革命は失速?[英エコノミスト]

米国のEV革命は失速?[英エコノミスト]

米国人は自動車が大好きだ。バッテリーで走らない限りは。ピュー・リサーチ・センターが7月に発表した世論調査によると、電気自動車(EV)の購入を検討する米国人は5分の2以下だった。充電網が絶えず拡大し、選べるEVの車種がますます増えているにもかかわらず、このシェアは前年をわずかに下回っている。 この言葉は、相対的な無策に裏打ちされている。2023年第3四半期には、バッテリー電気自動車(BEV)は全自動車販売台数の8%を占めていた。今年これまでに米国で販売されたEV(ハイブリッド車を除く)は100万台に満たず、自動車大国でない欧州の半分強である(図表参照)。中国のドライバーはその4倍近くを購入している。

By エコノミスト(英国)
労働者の黄金時代:雇用はどう変化しているか[英エコノミスト]

労働者の黄金時代:雇用はどう変化しているか[英エコノミスト]

2010年代半ばは労働者にとって最悪の時代だったという点では、ほぼ誰もが同意している。ロンドン・スクール・オブ・エコノミクスの人類学者であるデイヴィッド・グレーバーは、「ブルシット・ジョブ(どうでもいい仕事)」という言葉を作り、無目的な仕事が蔓延していると主張した。2007年から2009年にかけての世界金融危機からの回復には時間がかかり、豊かな国々で構成されるOECDクラブでは、労働人口の約7%が完全に仕事を失っていた。賃金の伸びは弱く、所得格差はとどまるところを知らない。 状況はどう変わったか。富裕国の世界では今、労働者は黄金時代を迎えている。社会が高齢化するにつれて、労働はより希少になり、より良い報酬が得られるようになっている。政府は大きな支出を行い、経済を活性化させ、賃上げ要求を後押ししている。一方、人工知能(AI)は労働者、特に熟練度の低い労働者の生産性を向上させており、これも賃金上昇につながる可能性がある。例えば、労働力が不足しているところでは、先端技術の利用は賃金を上昇させる可能性が高い。その結果、労働市場の仕組みが一変する。 その理由を理解するために、暗

By エコノミスト(英国)
中国は地球を救うのか、それとも破壊するのか?[英エコノミスト]

中国は地球を救うのか、それとも破壊するのか?[英エコノミスト]

脳腫瘍で余命いくばくもないトゥー・チャンワンは、最後の言葉を残した。その中国の気象学者は、気候が温暖化していることに気づいていた。1961年、彼は共産党の機関紙『人民日報』で、人類の生命を維持するための条件が変化する可能性があると警告した。 しかし彼は、温暖化は太陽活動のサイクルの一部であり、いつかは逆転するだろうと考えていた。トゥーは、化石燃料の燃焼が大気中に炭素を排出し、気候変動を引き起こしているとは考えなかった。彼の論文の数ページ前の『人民日報』のその号には、ニヤリと笑う炭鉱労働者の写真が掲載されていた。中国は欧米に経済的に追いつくため、工業化を急いでいた。 今日、中国は工業大国であり、世界の製造業の4分の1以上を擁する。しかし、その進歩の代償として排出量が増加している。過去30年間、中国はどの国よりも多くの二酸化炭素を大気中に排出してきた(図表1参照)。調査会社のロディウム・グループによれば、中国は毎年世界の温室効果ガスの4分の1以上を排出している。これは、2位の米国の約2倍である(ただし、一人当たりで見ると米国の方がまだひどい)。

By エコノミスト(英国)