Paxosアルゴリズム
Paxosとは信頼性が低いプロセッサのネットワークにおいて合意の問題を解決するためのプロトコルの集合である。 合意とは参加者のグループにおいて単一の結果について合意を得るプロセスである。参加者や通信手法に障害が起きる可能性がある場合、この問題は困難なものとなる[1]。
合意プロトコルは分散コンピューティングにおける状態機械アプローチの基礎であり、これはレスリー・ランポート[2]により提案され、Fred Schneiderによってサーベイがなされている[3]。
Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年であった[4]。 これ以前に、ナンシー・リンチ、Cynthia Dwork、Larry Stockmeyerは"部分同期"システムの広い範囲における合意形成方法を例証している。Paxosは分散トランザクションの文脈において、1988年にOkiとBarbara Liskovが発表したViewstampedレプリケーションにおける合意形成に使用されるプロトコルと非常に似ている[5]。
状態機械アプローチとはアルゴリズムをフォールトトレラントな、分散した実装に変換する技法である。アドホックな技術では重要な障害ケースが未解決 のままになる可能性がある。Lamport等によって定式化された手法では全てのケースが安全に処理されることを保証している。
Paxosプロトコル集合には次のものについてトレードオフを持っているような数種のものがある。
- プロセッサ数
- 合意された値を知るまでのメッセージ遅延
- 各ノードのアクティビティレベル
- 送信されたメッセージ数
- 障害の種類
Paxosプロトコル集合の共通の特徴は、不整合な状態に陥らないということがある[4][6][7][8][9]。
安全性と活性に関する特性
安全性を保証するため、Paxosは3つの安全性の特性を定義し、障害パターンによらず、これらが必ず守られていることを保証する。
- 非自明性
- 提案された値のみが習得される。[7]
- 完全性
- 最大一つの値が習得可能である。(つまり、2つの習得ノードがことなる値を習得することはない)[7][8]
- 活性(C;L)
- もし、値Cが提案されたならば、習得ノードLは何らかの値を習得する。(ただし十分数のプロセッサが障害を起こしていない場合)[8]
前提
Paxosの説明を単純化するため、次の前提や定義が明確化されなければならない。応用範囲を広げるための技術は文献に提示されており、当記事では触れない。詳細は外部リンクを参照のこと。
プロセッサ
- プロセッサは任意の速度で動作してもよい。
- プロセッサは障害が発生する可能性がある。
- 安定したストレージを持つプロセッサは障害の後、再参加可能である。
- プロセッサは共謀したり、誤った情報を返すなど、プロトコルの手続きを変えるようなことはしない。(任意の障害を容認する手法として、#ビザンチンPaxosを参照のこと)
ネットワーク
- プロセッサは他の全てのプロセッサにメッセージを送信することが可能である。
- メッセージは非同期的に送信され、到達までに任意の時間がかかることがある。
- メッセージは失われたり、順序を変更されたり、複製されることがある。
- メッセージは破損なしに配信される。(任意の障害を許容する手法として#ビザンチンPaxosを参照のこと)
プロセッサ数
一般に、分散合意アルゴリズムは
- Paxosアルゴリズムのページへのリンク
