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

  [[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人の王子を集め、董卓を攻撃しました。董卓を反逆者、袁紹を君主と定義し、忠臣が2人、裏切り者が1人います。曹操、劉備、孫堅（孫権の父）の3人の有力者を選択します。裏切り者は忠臣の役割を果たします。君主と2人の忠臣は裏切り者の正体を知らず、彼を忠臣として扱います。

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

董卓を排除するために、袁紹は忠臣たちの戦略を統一しなければなりません。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公式アカウントまでご連絡ください。