三国志を例に挙げて分散アルゴリズムについて語るのって、気楽なことでしょうか?

  [[357046]]

序文

「三国殺し」は、中国の三国時代を背景に、身分を手がかりにトランプを形にした人気のカードゲームです。教育的でありながらカジュアルで、あらゆる年齢層に適しています。

東漢末期、袁紹は同盟のリーダーとして18人の王子を集め、董卓を攻撃しました。

始める前に、分散プロトコルとアルゴリズムの全体的なコンテキストについて説明しましょう。

現在、多くの開発者は分散コンポーネントの使用方法についてある程度の経験があり、CAP 理論と BASE 理論の一般的な意味も知っています。しかし、分散アルゴリズムを真剣に検討する人はほとんどいません。これには3つの理由があります。

アルゴリズムが複雑すぎるのではないかと心配だったので、それにほとんど時間を費やしませんでした。

インターネット上には、分散アルゴリズムを平易な言葉で明確に説明できる情報が比較的少ないです。

分散アルゴリズムを学習するための明確な道筋はありません。

今後の記事では、ストーリーと平易な言葉を使って、分散アルゴリズムの原理と学習パスがどのようなものかを説明します。

学習パス

分散プロトコルとアルゴリズムを学習するには、まず基礎として 4 つの基本理論を学習し、次に基礎の上に家を建てるのと同じように、分散プロトコルとアルゴリズムを学習します。基礎が築かれて初めて、より安定した高層ビルを建てることができるのです。

4つの基本理論

• ビザンチン将軍問題
• CAP理論
• ACID理論
• ベース理論

8つの分散プロトコルとアルゴリズム

• Paxosアルゴリズム
• ラフトアルゴリズム
• 一貫性ハッシュアルゴリズム
• ゴシッププロトコルアルゴリズム
• クォーラムNWRアルゴリズム
• FBFTアルゴリズム
• POWアルゴリズム
• ZABプロトコル

スペースの制約により、この記事ではビザンチン将軍問題のみを取り上げます。

ビザンチン将軍問題

ビザンチン将軍問題という言葉を聞いたことがあるかもしれません。これは、レスリー・ランバートによって提案されたピアツーピア通信における基本的な問題です。

現在のトルコのイスタンブールに位置するビザンチウムは、東ローマ帝国の首都でした。当時のビザンチン・ローマ帝国は広大であったため、防衛目的を達成するために各軍は遠く離れており、将軍は伝言を伝達するために使者に頼るしかありませんでした。戦争中、ビザンチン軍のすべての将軍と副官は、敵陣を攻撃する前に勝利の可能性があるかどうかを判断するために全員一致の合意に達しなければなりませんでした。しかし、軍隊の中に裏切り者や敵のスパイがいる可能性があり、これがビザンチンのフォールト トレランス問題です。

実際、ビザンチン問題は分散分野における最も複雑なフォールト トレラント モデルです。一度理解すれば、分散コンセンサス問題の解決方法を習得できます。また、一般的に使用されるコンセンサス アルゴリズムを誰もが理解するのにも役立ち、作業において適切なアルゴリズムを選択したり、適切なアルゴリズムを設計したりするのに役立ちます。

最初の基本理論がビザンチン将軍問題であるのはなぜですか?

分散システムが直面するコンセンサスの問題を非常にうまく抽象化するためです。上記の 8 つの分散アルゴリズムのうち 5 つはビザンチン問題に関連しています。ビザンチン問題を理解すると、後で他のアルゴリズムを学ぶのがはるかに簡単になると言えます。

次に、三国志のゲームにおける身分カードを使用して、ビザンチン将軍問題について説明します。

三国殺し身分証

三国殺しには、主君、忠臣、反逆者、裏切り者の 4 つの主なアイデンティティがあります。各プレイヤーには身分証明書が渡されます。主はただ一人です。忠臣の最大数は 2 人、反逆者の最大数は 4 人、裏切り者の最大数は 1 人です。

主

領主IDカード

勝利条件: 裏切り者と裏切り者を全て排除する

ヒント: 自分自身の生存を第一の目標にして、反乱軍の注意をそらしましょう。忠誠派と協力して反乱軍を排除し、誰が忠誠者で誰が裏切り者かを判断します。

忠実な大臣

ロイヤルティIDカード

勝利条件: 領主の生存を守りながら、反乱者と裏切り者をすべて排除する。

スキル: 忠実な大臣は領主の盾であり、反逆者や裏切り者を抑止するバランスです。

泥棒対策

盗難防止IDカード

勝利条件: 領主を破壊して勝利する。

ヒント: 反乱軍は最大の集団であるため、火力を集中させて敵の弱点を攻撃する必要があります。正しい考え方が勝利への鍵です。

裏切り者

裏切り者IDカード

勝利条件: まず反乱軍と忠実な大臣を排除し、最後に領主と戦って最後の生き残りとなる。

ヒント: 正しい戦術 + 冷静な判断 + 運。

ビザンチン問題の修復

東漢末期、袁紹は同盟のリーダーとして18人の王子を集め、董卓を攻撃しました。董卓を反逆者、袁紹を君主とすると、忠臣が二人と裏切り者が一人いることになります。影響力のある 3 人の人物、曹操、劉備、孫堅 (孫権の父) を選択してください。裏切り者は忠実な大臣の役を演じる。藩主と二人の忠臣は裏切り者の正体を知らず、彼を忠臣として扱う。

董卓は非常に強力でした。彼の指揮下には、よく訓練された西涼の兵士と軍神である呂布がいた。呂布が劉備、張飛、関羽と単独で戦った「呂布に立ち向かう三英雄」の物語は誰もが知っています。

董卓を排除するために、袁紹は忠臣たちの戦略を統一しなければならなかった。 3人の忠臣が他にどんな策略を持っているかは不明だが、そのうちの1人は裏切り者である。裏切り者が反逆者の董卓と密かに連絡を取り、忠臣たちに誤解を招くような戦闘情報を送っていたら、どうすればいいでしょうか?また、これらの忠臣たちが手紙を通じて戦闘情報を交換していると仮定すると、手紙が傍受されたり、手紙内の情報が置き換えられたりしたらどうなるでしょうか?これらのシナリオは戦闘計画を混乱させる可能性があり、最終的には一部の忠実な大臣が攻撃し、他の大臣が撤退することになります。そうすれば、反乱軍はこの機会を利用して攻撃を開始し、彼らを一人ずつ倒すことができます。

袁紹は曹操ほどの機転を利かせることができなかったが、忠実な臣下たちを説得して統一された作戦を立てさせるにはどうすればよいのだろうか。

上記のマッピング関係は、ビザンチン将軍問題を簡略化して表現したものです。袁紹が現在直面しているのは、典型的なコンセンサス問題だ。つまり、誤解を招く情報が存在する可能性がある場合には、複数の将軍が合意に達し、一貫した戦闘計画を策定できるように、適切なコミュニケーションメカニズムを採用する必要がある。

一方は撤退を選択

劉備、曹操、孫堅は使者を通じて攻撃か撤退かの情報を伝え、攻撃するか撤退するかを交渉した。多数決ルールが遵守され、棄権は認められません。

曹操は大いに疑い、反乱軍の地形を偵察した後、撤退することにした。劉備と孫堅は攻撃を決意した。

• 劉備は攻撃を決意し、曹操と孫堅に攻撃するよう伝える使者を送った。
• 曹操は撤退を決意し、劉備と孫堅に撤退するよう伝える使者を送った。
• 孫堅は攻撃を決意し、曹操と劉備に攻撃するよう伝える使者を送った。

一方は撤退を選択

曹操が受け取った情報：攻撃に2票、撤退に1票。投票を比較すると、攻撃票と撤退票の比率は 2:1 になります。少数は多数に従うという原則に従って、曹操は依然として攻撃を続けます。すると、3者の戦闘計画はいずれも攻撃的なものとなり、一貫した戦闘計画となります。ついに董卓を倒した。

裏切り者出現 - 撤退

初期設定では、孫堅は裏切り者としてすでに反逆者の董卓と個人的に連絡を取り、董卓を攻撃しないことを決めていました。

• 劉備は攻撃を決意し、曹操と孫堅に攻撃するよう伝える使者を送った。
• 曹操は撤退を決意し、曹操と孫堅に撤退するよう伝える使者を送った。
• 孫堅は撤退を決意し、曹操と劉備に撤退するよう伝える使者を送った。

裏切り者出現 - 撤退

劉備は攻撃と撤退にそれぞれ 1 票ずつ与えられ、撤退を選択したため、劉備が得た票数は、攻撃: 撤退 = 1:2 でした。少数は多数に従うという原則に従い、劉備は最終的に撤退することを選択した。すると、3つの陣営の作戦はいずれも撤退することになり、これも一貫した作戦だった。

裏切り者 - 一歩前進して一歩後退

裏切り者は上記の計画を読んで、忠臣たちが全員撤退して排除されていないことに気づき、不正行為をして忠臣の一人を排除しようとしました。

• 劉備は攻撃を決意し、曹操と孫堅に攻撃するよう伝える使者を送った。
• 曹操は撤退を決意し、曹操と孫堅に撤退するよう伝える使者を送った。
• 孫堅は裏切り者として使者を送り、劉備に攻撃を、曹操に撤退を命じた。

裏切り者 - 一歩前進して一歩後退

それで結果はどうでしょうか?

劉備の票は攻撃に2票、撤退に1票、曹操の票は攻撃に1票、撤退に2票です。少数が多数に従うという原則によれば、劉備は最終的に攻撃を選択し、曹操は撤退を選択することになるだろう。孫堅は裏切り者なので絶対に攻撃しないだろう。劉備は単独で反乱軍の董卓を攻撃したが、数で劣勢に立たされ、董卓に殺された。

この場面から、裏切り者の孫堅が誤った情報を送り、劉備と曹操の作戦を簡単に妨害し、その結果、二人の忠臣が次々と倒されていったことがわかります。この現象は、2つの忠誠心と1つの判断の問題です。では、袁紹公はこの問題をどう解決すべきでしょうか?

ビザンチン問題の解決

解決原理

つまり、袁紹に投票に参加させ、忠臣の数を増やすのです。忠実な大臣3人と裏切り者1人。そして、4人の将軍は、命令が来ない場合は撤退などの既定の命令を実行するという合意を結んだ。さらに、戦闘情報を送信するプロセスと戦闘命令を実行する方法についても合意されています。この解決策の重要なポイントは、戦闘情報の協議を 2 回実行することです。

最初のラウンドがどのように行われたかを見てみましょう。

• ステップ 1: 最初に戦闘情報を送信する将軍を司令官 (袁紹) と呼び、他の将軍を副官 (劉備、曹操、孫堅) と呼びます。
• ステップ 2: 指揮官は戦闘情報をすべての中尉に送信します。
• ステップ 3: 各副官は指揮官から受け取った戦闘情報を自身の戦闘命令として使用します。指揮官から戦闘情報を受け取らない場合は、戦闘命令としてデフォルトの退却を実行します。

図を使って説明しましょう。袁紹は主君として最初に戦闘情報を送り、戦闘命令は攻撃することです。すると曹操、劉備、孫堅は攻撃命令を受けた。

第1ラウンド

第2ラウンドがどのように行われたか見てみましょう。

• 第一陣の指揮官（袁紹）が命令を出した。今度は劉備、曹操、孫堅が順番に指揮官として行動し、他の2人の副将軍に戦闘情報を送る必要があります。
• そして、三人の副将軍は、少数は多数に従うという原則に従って、受けた戦闘命令を遂行した。

孫堅の策略 - 2回の撤退

たとえば、孫堅が不正行為をした場合、下の図に示すように、曹操と劉備の両方に撤退メッセージを送信します。すると劉備と曹操が受け取った戦闘情報は攻撃に2票、撤退に1票でした。少数が多数に従うという原則に従って、劉備と曹操は最終的に攻撃を実行し、戦闘計画の一貫性を達成しました。曹操と劉備は共に戦い、反乱軍の董卓を倒した（孫堅は戦闘に参加しなかった）。

孫堅の策略 - 2回の撤退

孫堅の策略 - 前進と後退

もし孫堅がズルをして曹操に撤退命令を出し、劉備に攻撃命令を出した場合、劉備が受け取る戦闘情報は攻撃3票となり、確実に攻撃を仕掛けることになりますが、曹操が受け取る戦闘情報は攻撃2票、撤退1票となり、曹操は結局攻撃を仕掛けることになります。そのため、劉備と曹操は力を合わせて反逆者董卓を倒すことになります。

指揮官を導入することで確かに孫堅の不正行為を防止できるようですが、第 1 ラウンドで孫堅が指揮官で、他の者が副官だった場合はどうなるでしょうか。

孫堅の策略 - 前進と後退

孫堅が司令官となる

第一ラウンドでは、孫堅は副官の一人である袁紹に撤退命令を出し、他の二人の副官である曹操と劉備に攻撃命令を出した。第1ラウンドの結果は次のとおりです。

第1ラウンド

第二ラウンドでは、孫堅は休憩を取り、孫堅から送られた指示に従って、他の副官が他の副官に指示を送り始めました。

• 曹操は劉備と袁紹に攻撃命令を出した。
• 劉備は曹操と袁紹に攻撃命令を出した。
• 袁紹は曹操と劉備に撤退命令を出した。

下の図に示すように、曹操、劉備、袁紹が受け取った最終指示は、攻撃に2票、撤退に1票でした。少数は多数に従うという原則に従い、3人全員が攻撃を開始した。作戦の勝利を確実にするために一貫した戦闘計画が実行された。

第2ラウンド

まとめ

上記のデモンストレーションを通じて、ビザンチン将軍問題を解決する方法がわかりました。実際、ランバート氏は論文の中でこの問題の解決方法についても言及しています。

反乱軍の将軍の数が m で、将軍の数 n >= 3m + 1 の場合、ビザンチン将軍問題は解決できます。

前提条件: 反乱軍の将軍の数が同じであり、m + 1 ラウンドの戦闘交渉が必要です。

この式を覚えておけば、導出のプロセスについては論文を参照することができます。

例えば、前述の董卓を攻める問題では、曹操、劉備、孫堅のうち、孫堅は反逆の将軍でした。彼は不正行為をして、戦闘計画に一貫性を欠く可能性がある。一貫した戦略を立てるためには、忠臣である袁紹を加えて合意形成を図らなければなりません。

ビザンチンソリューション2 - 署名

忠実な大臣の数を増やさずに、ビザンツ帝国における 2 人の忠実な大臣と 1 人の裁判官の問題をどのように解決できるでしょうか。

解決策 2 は、メッセージに署名することです。たとえば、将軍たちは印章や虎の紋章、その他の象徴を通して互いに連絡を取り合っていました。これらの特性を確保するには:

• 署名は偽造できず、署名されたメッセージの内容の変更は検出されます。
• 誰でも将軍の署名の真正性を検証できる。

スペースの制限により、ここでは署名のデモンストレーションについて詳しく説明しません。ご興味がございましたら、@ してください。後ほど追加します。

要約する

分散コンピューティングにおけるコンセンサス シナリオを、三国志ゲームのキャラクターを通じて説明します。では、それらは分散システムにどのようにマッピングされるのでしょうか?

• 将軍はコンピュータノードに対応します。
• 忠実な将軍は正常に機能しているコンピュータ ノードに相当します。
• 反逆将軍は、誤動作して誤解を招く情報を送信しているコンピュータ ノードに対応します。
• メッセンジャーの殺害は、通信障害と情報損失に相当します。
• スパイによる宅配業者の置き換えは、通信に対する悪意のある攻撃、偽造情報、または通信のハイジャックに相当します。

ビザンチン問題を過小評価しないでください。これは分散シナリオにおける最も複雑な障害シナリオです。例えば、これらの知識ポイントは、デジタル通貨のブロックチェーン技術で使用されています。また、ビザンチンフォールトトレランスアルゴリズム (BFT) を使用する必要があります。

ビザンチンフォールトトレラントアルゴリズム、FBFT アルゴリズム、PoW アルゴリズムがあります。もちろん、この記事ではこれらのアルゴリズムについては説明しません。後ほど説明します。太った男は一口では食べられないよ～

ビザンチン フォールト トレラント アルゴリズムでは、非ビザンチン フォールト トレラント アルゴリズムが存在する必要があります。これは、名前が示すように、誤解を招く情報を送信するノードが存在しないことを意味します。 CFT アルゴリズムは、障害はあるが悪意のあるノードがない分散システムにおけるコンセンサスの問題を解決します。簡単に言えば、システム障害によりメッセージが失われたり重複したりする可能性がありますが、エラー メッセージや偽造されたメッセージはありません。対応するアルゴリズムには、Paxos アルゴリズム、Raft アルゴリズム、ZAB プロトコルなどがあります。追記説明〜

上記の 5 つのアルゴリズムはすべてビザンチン問題に関連しています。今日私たちが話しているビザンチン問題は重要だと思いますか?

非常に多くのアルゴリズムからどのように選択すればよいのでしょうか?

ノードは信頼できるため、非ビザンチン フォールト トレラント アルゴリズムが選択されます。それ以外の場合は、ブロックチェーンで使用される PoW アルゴリズムなどのビザンチンフォールトトレラントアルゴリズムを使用します。

この記事はWeChatの公開アカウント「Wukong Chats about Architecture」から転載したものです。下のQRコードからフォローできます。この記事を転載する場合はWukong Chat Architecture公式アカウントまでご連絡ください。