PAXOSアルゴリズム

Paxosとは信頼性が低いプロセッサのネットワークにおいて合意の問題を解決するためのプロトコルの集合である。合意とは参加者のグループにおいて単一の結果について合意を得るプロセスである。参加者や通信手法に障害が起きる可能性がある場合、この問題は困難なものとなる。合意プロトコルは分散コンピューティングにおける状態機械アプローチの基礎であり、これはレスリー・ランポートにより提案され、Fred Schneiderによってサーベイがなされている。Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年であった。これ以前に、Nancy Lynch、Cynthia Dwork、Larry Stockmeyerは\"部分同期\"システムの広い範囲における合意形成方法を[http://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf 例証している]。Paxosは分散トランザクションの文脈において、1988年にOkiとBarbara Liskovが発表したViewstampedレプリケーションにおける合意形成に使用されるプロトコルと非常に似ている。状態機械アプローチとはアルゴリズムをフォールトトレラントな、分散した実装に変換する技法である。アドホックな技術では重要な障害ケースが未解決のままになる可能性がある。Lamport等によって定式化された手法では全てのケースが安全に処理されることを保証している。Paxosプロトコル集合には次のものについてトレードオフを持っているような数種のものがある。*プロセッサ数*合意された値を知るまでのメッセージ遅延*各ノードのアクティビティレベル*送信されたメッセージ数*障害の種類Paxosプロトコル集合の共通の特徴は、不整合な状態に陥らないということがある。