コンセンサス（コンピュータサイエンス）

分散コンピューティングとマルチエージェント システムの基本的な問題は、多数の障害のあるプロセスが存在する状況でシステム全体の信頼性を実現することです。これには、多くの場合、プロセスを調整してコンセンサスに達するか、計算中に必要なデータ値に同意する必要があります。コンセンサスの応用例としては、どのトランザクションをどの順序でデータベースにコミットするかの合意、ステート マシンのレプリケーション、アトミック ブロードキャストなどがあります。コンセンサスを必要とすることが多い実際のアプリケーションには、クラウド コンピューティング、クロック同期、PageRank、意見形成、スマート電力網、状態推定、UAV (および一般に複数のロボット/エージェント) の制御、負荷分散、ブロックチェーンなどがあります。

コンセンサスの問題では、単一のデータ値について多数のプロセス (またはエージェント) 間で合意する必要があります。プロセス (エージェント) の中には、他の点で障害が発生したり、信頼性が低かったりするものがある可能性があるため、コンセンサス プロトコルはフォールト トレラントまたは回復力を備えている必要があります。プロセスは候補値を提示し、相互に通信して、単一のコンセンサス値に合意する必要があります。

合意問題は、マルチエージェント システムを制御する上での基本的な問題です。合意を生成するための 1 つの方法は、すべてのプロセス (エージェント) が多数決の値に同意することです。この場合、多数決には、利用可能な投票数の少なくとも半数以上が必要です (各プロセスに 1 票が与えられます)。ただし、1 つ以上の欠陥のあるプロセスによって結果が歪められ、合意に達しなかったり、誤って達したりする可能性があります。

合意問題を解決するプロトコルは、限られた数の障害のあるプロセスに対処するように設計されています。これらのプロトコルが有用であるためには、いくつかの要件を満たす必要があります。たとえば、単純なプロトコルでは、すべてのプロセスがバイナリ値 1 を出力する可能性があります。これは有用ではありません。したがって、要件は、出力が入力に依存するように変更されます。つまり、合意プロトコルの出力値は、何らかのプロセスの入力値である必要があります。もう 1 つの要件は、プロセスが出力値を 1 回だけ決定し、この決定を取り消すことができないことです。メソッドは、実行時に障害が発生しない場合に正しいとされます。停止障害を許容する合意プロトコルは、次のプロパティを満たす必要があります。^[1]

終了

最終的には、すべての正しいプロセスが何らかの値を決定します。

誠実さ

すべての正しいプロセスが同じ値を提案した場合、どの正しいプロセスも を決定する必要があります。${\displaystyle v}$${\displaystyle v}$

合意

すべての正しいプロセスは同じ値に同意する必要があります。

アプリケーションによっては、整合性の定義にバリエーションを加えることが適切である場合があります。たとえば、より弱い^{[さらなる説明が必要]}タイプの整合性は、決定値が、必ずしもすべての正しいプロセスが提案した値と等しいというものです。^[1]また、文献には、プロセスによって送信されたメッセージが配信される必要があるという特性を指す、妥当性と呼ばれる条件もあります。 ^[1]

最大で t 個のプロセスが失敗しても n 個のプロセス間で正しく合意が得られることを保証できるプロトコルは、t 耐性があると言われます。

コンセンサス プロトコルのパフォーマンスを評価する際に、重要な 2 つの要素は実行時間とメッセージの複雑さです。実行時間は、入力パラメータ (通常はプロセス数や入力ドメインのサイズ) の関数として、メッセージ交換のラウンド数でBig O 表記法で表されます。メッセージの複雑さは、プロトコルによって生成されるメッセージ トラフィックの量を指します。その他の要素には、メモリ使用量やメッセージのサイズなどがあります。

さまざまな計算モデルが「コンセンサス問題」を定義する場合があります。一部のモデルは完全に接続されたグラフを扱い、他のモデルはリングとツリーを扱います。一部のモデルではメッセージ認証が許可されますが、他のモデルではプロセスは完全に匿名です。プロセスが共有メモリ内のオブジェクトにアクセスして通信する共有メモリ モデルも、重要な研究分野です。

通信プロトコルのほとんどのモデルでは、参加者は認証されたチャネルを介して通信します。つまり、メッセージは匿名ではなく、受信者は受信したすべてのメッセージの送信元を知っています。一部のモデルでは、より強力で転送可能な認証形式を想定しています。この認証形式では、各メッセージは送信者によって署名され、受信者はすべてのメッセージの直接の送信元だけでなく、メッセージを最初に作成した参加者も知っています。この強力なタイプの認証はデジタル署名によって実現され、この強力な認証形式が利用できる場合、プロトコルはより多くの障害を許容できます。^[2]

2つの異なる認証モデルは、口頭コミュニケーションモデルと書面コミュニケーションモデルと呼ばれることが多い。口頭コミュニケーションモデルでは、情報の直接的なソースがわかっているが、より強力な書面コミュニケーションモデルでは、受信者はメッセージの直接的なソースだけでなく、メッセージのコミュニケーション履歴を各ステップで学習する。^[3]

Paxosなどの最も伝統的な単一値コンセンサス プロトコルでは、協力するノードは、データベースにコミットされたトランザクションなどの 有用なメタデータをエンコードするために、可変サイズの整数などの単一の値に同意します。

単一値コンセンサス問題の特殊なケースであるバイナリ コンセンサスは、入力、つまり出力ドメインを単一のバイナリ ディジット {0,1} に制限します。バイナリ コンセンサス プロトコルは、それ自体ではあまり有用ではありませんが、より一般的なコンセンサス プロトコル、特に非同期コンセンサスの構成要素として役立つことがよくあります。

Multi-PaxosやRaftなどの多値コンセンサス プロトコルでは、単一の値だけでなく、時間の経過とともに一連の値に合意し、徐々に成長する履歴を形成することが目標です。多値コンセンサスは、単一値のコンセンサス プロトコルを連続して複数回反復実行することで単純に達成できますが、多くの最適化や再構成のサポートなどの他の考慮事項により、実際には多値コンセンサス プロトコルをより効率的にすることができます。

プロセスが受ける可能性のある障害には、クラッシュ障害とビザンチン障害の 2 種類があります。クラッシュ障害は、プロセスが突然停止し、再開しない場合に発生します。ビザンチン障害は、まったく条件が課されない障害です。たとえば、攻撃者の悪意のある行為の結果として発生することがあります。ビザンチン障害が発生するプロセスは、矛盾したデータを他のプロセスに送信したり、スリープ状態になってから長時間の遅延の後にアクティビティを再開したりすることがあります。2 種類の障害のうち、ビザンチン障害の方がはるかに破壊的です。

したがって、ビザンチン障害を許容するコンセンサス プロトコルは、発生する可能性のあるあらゆるエラーに対して耐性を持つ必要があります。

ビザンチン障害を許容するコンセンサスのより強力なバージョンは、整合性制約を強化することによって得られます。

誠実さ

正しいプロセスが を決定する場合、 は何らかの正しいプロセスによって提案されている必要があります。${\displaystyle v}$${\displaystyle v}$

合意問題は、非同期システムまたは同期システムの場合に考慮される可能性があります。現実世界の通信は本質的に非同期であることが多いですが、非同期システムは同期システムよりも当然多くの問題を伴うため、同期システムをモデル化する方が実用的で簡単です。 ^[4]

同期システムでは、すべての通信がラウンドで進行すると想定されています。 1 ラウンドで、プロセスは必要なすべてのメッセージを送信し、他のプロセスからのすべてのメッセージを受信します。 このように、1 つのラウンドのメッセージは、同じラウンド内で送信されるメッセージに影響を与えることはありません。

少なくとも 1 つのプロセスがクラッシュ障害を起こす可能性がある、完全に非同期のメッセージ パッシング分散システムでは、フィッシャー、リンチ、パターソンによる1985 年の有名なFLP 不可能性結果で、合意を達成するための決定論的アルゴリズムは不可能であることが証明されました。^{[5]この不可能性結果は、最悪のケースのスケジューリング シナリオから派生したもので、ネットワーク内のインテリジェント}なサービス拒否攻撃者などの敵対的な状況を除いて、実際には発生する可能性は低いです。ほとんどの通常の状況では、プロセス スケジューリングにはある程度の自然なランダム性があります。^[4]

非同期モデルでは、いくつかの形式の障害は同期コンセンサス プロトコルによって処理できます。たとえば、通信リンクの損失は、ビザンチン障害が発生したプロセスとしてモデル化できます。

ランダム化コンセンサスアルゴリズムは、ネットワーク内のインテリジェントなサービス拒否攻撃者などの最悪のスケジュールシナリオ下でも、安全性と生存性を圧倒的な確率で達成することで、FLP不可能性結果を回避できます。^[6]

合意アルゴリズムは、参加ノードのセットが固定されており、最初から与えられていると従来想定しています。つまり、何らかの事前 (手動または自動) 構成プロセスによって、グループのメンバーとして相互に認証できる特定の既知の参加者グループが許可されているということです。認証されたメンバーを含む、明確に定義されたクローズド グループがない場合、オープンな合意グループに対するシビル攻撃は、フォールト トレランスのしきい値を超えるだけの仮想参加者を作成するだけで、ビザンチン合意アルゴリズムさえも破ることができます。

対照的に、許可のないコンセンサスプロトコルでは、ネットワーク内の誰もが事前の許可なしに動的に参加できますが、代わりにシビル攻撃の脅威を軽減するために別の形の人工的なコストまたは参入障壁を課します。ビットコインは、プルーフ オブ ワークと難易度調整機能を使用した最初の許可のないコンセンサス プロトコルを導入しました。このプロトコルでは、参加者が暗号ハッシュパズルを解くために競争し、ブロックをコミットする権利を確率的に獲得し、投資した計算努力に比例した関連する報酬を獲得します。 このアプローチのエネルギー コストが高いことに一部動機付けられて、その後の許可のないコンセンサス プロトコルでは、プルーフ オブ ステーク、プルーフ オブ スペース、プルーフ オブ オーソリティなど、シビル攻撃からの保護のための他の代替参加ルールが提案または採用されています。

興味深い合意問題は次の3つです。

から番号が付けられたプロセスの集合で、互いにメッセージを送信して通信します。プロセスは、次の条件を満たすすべてのプロセスに 値を送信する必要があります。${\displaystyle n}$${\displaystyle 0}$${\displaystyle n-1,}$${\displaystyle 0}$${\displaystyle v}$

1. プロセスが正しければ、すべての正しいプロセスは${\displaystyle 0}$${\displaystyle v}$
2. 任意の 2 つの正しいプロセスの場合、各プロセスは同じ値を受け取ります。

これは将軍の問題としても知られています。

コンセンサス プロトコルの正式な要件には、次のようなものが含まれます。

• 合意: すべての正しいプロセスは同じ値に同意する必要があります。
• 弱い妥当性: 正しいプロセスごとに、その出力は何らかの正しいプロセスの入力である必要があります。
• 強い妥当性: すべての正しいプロセスが同じ入力値を受け取った場合、それらはすべてその値を出力する必要があります。
• 終了: すべてのプロセスは最終的に出力値を決定する必要がある

部分的に同期したシステム（同期の良い期間と悪い期間が交互に繰り返される）におけるn個のプロセスでは、各プロセスがプライベート値を選択する。プロセスはラウンドごとに相互に通信してパブリック値を決定し、以下の要件を満たすコンセンサスベクトルを生成する。^[7]

1. 正しいプロセスが を送信すると、すべての正しいプロセスは のいずれかを受信するか、何も受信しない (整合性プロパティ)${\displaystyle v}$${\displaystyle v}$
2. 正しいプロセスによって 1 ラウンドで送信されたすべてのメッセージは、すべての正しいプロセスによって同じラウンドで受信されます (一貫性プロパティ)。

これらの問題のバリエーションは、あるタイプのモデルにおける問題の解決策が、別のタイプのモデルにおける別の問題の解決策になる可能性があるという点で同等であることが示されています。たとえば、同期認証メッセージパッシングモデルにおける弱いビザンチン一般問題の解決策は、弱いインタラクティブ一貫性の解決策につながります。^[8]インタラクティブ一貫性アルゴリズムは、各プロセスがコンセンサスベクトルの多数決値をコンセンサス値として選択することで、コンセンサス問題を解決できます。^[9]

ビザンチン将軍問題^[10] [ ^11]を解決するt耐性匿名同期プロトコルがあり、弱いビザンチン将軍の場合^[8]は失敗の数、プロセスの数です。 ${\displaystyle {\tfrac {t}{n}}<{\tfrac {1}{3}}}$${\displaystyle t}$${\displaystyle n}$

ビザンチンプロセッサを持つシステムでは、口頭メッセージモデルにおける合意問題を解決するアルゴリズムは存在しないことが示されている。^[12]証明は、まず3ノードの場合の不可能性を示し、この結果を使用してプロセッサの分割について議論することによって構築される。書面メッセージモデルでは、を許容できるプロトコルが存在します。^[2]${\displaystyle n}$${\displaystyle f}$${\displaystyle n\leq 3f}$${\displaystyle n=3}$${\displaystyle n=f+1}$

完全に非同期のシステムでは、非自明性のみを要求する場合でも、1回以上のクラッシュ障害を許容できるコンセンサスソリューションは存在しません。^{[5]この結果は、この重要な研究により}ダイクストラ賞を受賞した著者のマイケル・J・フィッシャー、ナンシー・リンチ、マイク・パターソンにちなんで、FLP不可能性証明と呼ばれることもあります。 FLPの結果は、公平性の仮定の下でも保持されることが機械的に検証されています。^[13]ただし、FLPはコンセンサスに決して到達できないとは述べていません。モデルの仮定の下では、限られた時間内に常にコンセンサスに到達できるアルゴリズムはない、と述べているだけです。実際には、それが起こる可能性は非常に低いです。

Leslie LamportによるPaxosコンセンサス アルゴリズム、およびRaftなどのその派生版は、広く導入されている分散コンピューティング システムやクラウド コンピューティングシステムで広く使用されています。これらのアルゴリズムは通常、同期型で、進行には選出されたリーダーに依存し、クラッシュのみを許容し、ビザンチン障害は許容しません。

ビザンチン障害を許容する多項式時間バイナリ合意プロトコルの例としては、Garay と Berman による Phase King アルゴリズムがあります。^{[14]このアルゴリズムは、} n 個のプロセスと最大f 個の障害 ( n > 4 f ) を伴う同期メッセージ パッシング モデルで合意を解決します。Phase King アルゴリズムにはf + 1 フェーズがあり、フェーズごとに 2 ラウンドあります。各プロセスは、その優先出力 (最初はプロセス自身の入力値に等しい) を追跡します。各フェーズの最初のラウンドでは、各プロセスは自身の優先値を他のすべてのプロセスにブロードキャストします。次に、すべてのプロセスから値を受信し、どの値が多数決値であるか、およびその数を決定します。フェーズの 2 番目のラウンドでは、ID が現在のフェーズ番号と一致するプロセスが、そのフェーズのキングに指定されます。キングは最初のラウンドで観測した多数決値をブロードキャストし、タイブレーカーとして機能します。プロセスが最初のラウンドで観測した多数決値の数がn /2 + fより大きい場合、プロセスはその優先順位をその多数決値に変更します。それ以外の場合は、フェーズ キングの値を使用します。 f + 1 フェーズの終了時に、プロセスは優先順位の値を出力します。

GoogleはChubbyと呼ばれる分散ロックサービスライブラリを実装しました。^[15] Chubbyは、障害発生時に高い可用性を実現するために、複製されたデータベースに保存される小さなファイルにロック情報を保持します。データベースは、Paxosコンセンサスアルゴリズムに基づくフォールトトレラントログレイヤーの上に実装されています。このスキームでは、Chubbyクライアントは、複製されたログにアクセス/更新するために、つまり、ファイルへの読み取り/書き込みを行うために、Paxosマスターと通信します。 ^[16]

多くのピアツーピアのオンラインリアルタイム ストラテジーゲームでは、ゲーム内のプレイヤー間のゲーム状態を管理するために、コンセンサス プロトコルとして修正されたロックステップ プロトコルを使用しています。ゲームの各アクションにより、ゲーム状態デルタがゲーム内の他のすべてのプレイヤーにブロードキャストされ、ゲーム状態全体のハッシュも送信されます。各プレイヤーは、デルタを自分のゲーム状態に適用し、ゲーム状態ハッシュを比較することで変更を検証します。ハッシュが一致しない場合は投票が行われ、ゲーム状態が少数派のプレイヤーは切断され、ゲームから削除されます (desync と呼ばれます)。

もう一つのよく知られたアプローチはMSR型アルゴリズムと呼ばれ、コンピュータサイエンスから制御理論まで広く使われてきました。^{[17] [18] [19]}

ビットコインは、オープンなピアツーピアネットワークで許可のない合意を得るために、プルーフオブワーク、難易度調整機能、再編成機能を使用しています。ビットコインのブロックチェーン、つまり分散型台帳を拡張するために、マイナーは暗号パズルを解こうとします。このパズルでは、解が見つかる確率は、1秒あたりのハッシュで費やされる計算量に比例します。最初にそのようなパズルを解いたノードは、提案された次のトランザクションブロックのバージョンを台帳に追加され、最終的に他のすべてのノードに受け入れられます。ネットワーク内のどのノードもプルーフオブワーク問題の解決を試みることができるため、攻撃者がネットワークの計算リソースの50%以上を持っていない限り、シビル攻撃は原理的に実行不可能です。

他の暗号通貨（例：イーサリアム、NEO、STRATISなど）はプルーフ・オブ・ステークを使用しており、ノードはブロックを追加するために競争し、ステーク、つまり一定期間割り当てられロックまたはステークされた既存の暗号通貨に比例した報酬を獲得します。プルーフ・オブ・ステークが「プルーフ・オブ・ワーク」システムよりも優れている点の1つは、後者ではエネルギー消費量が高いことです。例えば、ビットコインマイニング（2018年）は、チェコ共和国またはヨルダンの国家全体と同量の非再生エネルギー源を消費すると推定されていますが、最大のプルーフ・オブ・ステークネットワークであるイーサリアムの総エネルギー消費量は、米国の平均的な家庭205世帯の消費量をわずかに下回ります。^{[29] [30] [31]}

リップルなどの一部の暗号通貨では、台帳を検証するために検証ノードのシステムを使用しています。リップルが使用するこのシステムは、リップル プロトコル コンセンサス アルゴリズム (RPCA) と呼ばれ、ラウンドで動作します。

ステップ 1: すべてのサーバーが有効な候補トランザクションのリストをコンパイルします。

ステップ 2: 各サーバーは、そのユニーク ノード リスト (UNL) からのすべての候補を統合し、その信憑性について投票します。

ステップ 3: 最小しきい値を通過したトランザクションは次のラウンドに渡されます。

ステップ4：最終ラウンドでは80％の合意が必要です。^[32]

参加障壁を課し、シビル攻撃に抵抗するために許可のないコンセンサス プロトコルで使用されるその他の参加ルールには、権限の証明、スペースの証明、バーンの証明、経過時間の証明などがあります。

上記の許可なしの参加ルールはいずれも、何らかの行動やリソースへの投資額に比例して参加者に報酬を与えるものですが、人格証明プロトコルは、経済的投資額に関係なく、許可なしのコンセンサスにおいて実際の人間の参加者それぞれに正確に1単位の投票権を与えることを目指しています。^{[33] [34]}人格証明のためのコンセンサス権を1人1つに分配するための提案されたアプローチには、物理​​的な仮名パーティ、^[35]ソーシャルネットワーク、^[36]仮名化された政府発行のID、^[37]および生体認証があります。^[38]

共有メモリ システムにおける合意問題を解決するには、並行オブジェクトを導入する必要があります。並行オブジェクト (共有オブジェクト) は、並行プロセスが通信して合意に達するのに役立つデータ構造です。クリティカル セクションを使用する従来の実装では、クリティカル セクション内でプロセスが停止したり、許容できないほど長時間スリープ状態になったりすると、クラッシュするリスクがあります。研究者は、待機フリーを、アルゴリズムが有限数のステップで完了することを保証するものと定義しました。

並行オブジェクトのコンセンサス数は、待機なしの実装で特定のオブジェクトがコンセンサスに達することができるシステム内のプロセスの最大数として定義されます。^[39]コンセンサス数が のオブジェクトは、コンセンサス数が またはそれ以下のオブジェクトを実装できますが、それより高いコンセンサス数のオ​​ブジェクトを実装することはできません。コンセンサス数は、ハーリヒの同期オブジェクトの階層と呼ばれるものを形成します。^[40]${\displaystyle n}$${\displaystyle n}$

階層構造によれば、読み取り/書き込みレジスタは2プロセスシステムでもコンセンサスを解決できない。スタックやキューなどのデータ構造は、2つのプロセス間のコンセンサスしか解決できない。しかし、一部の並行オブジェクトはユニバーサル（表では と表記）であり、任意の数のプロセス間でコンセンサスを解決でき、操作シーケンスを通じて他のオブジェクトをシミュレートできる。^[39]${\displaystyle \infty}$

• 統一された合意
• 量子ビザンチン協定
• ビザンチン断層

• Herlihy, M.; Shavit, N. (1999). 「非同期計算可能性のトポロジカル構造」Journal of the ACM . 46 (6): 858. CiteSeerX  10.1.1.78.1455 . doi :10.1145/331524.331529. S2CID  5797174.
• Saks, M.; Zaharoglou, F. (2000). 「待機なしの k セット合意は不可能: 公開知識のトポロジー」SIAM Journal on Computing . 29 (5): 1449–1483. doi :10.1137/S0097539796307698.
• バシール、イムラン。「ブロックチェーンコンセンサス」。ブロックチェーンコンセンサス - 古典、ブロックチェーン、量子コンセンサスプロトコル入門。ISBN 978-1-4842-8178-9 Apress、カリフォルニア州バークレー、2022年。doi : 10.1007 /978-1-4842-8179-6