Paxosアルゴリズムのソースを表示

'''Paxos'''とは信頼性が低いプロセッサのネットワークにおいて[[合意_(情報工学)|合意]]の問題を解決するためのプロトコルの集合である。
'''合意'''とは参加者のグループにおいて単一の結果について合意を得るプロセスである。参加者や通信手法に障害が起きる可能性がある場合、この問題は困難なものとなる<ref name=agree>{{cite journal<!--|curly=yes-->|last=Pease|first=Marshall|coauthors=Robert Shostak, Leslie Lamport|year=1980|month=April|title=Reaching Agreement in the Presence of Faults|journal=[[Journal of the Association for Computing Machinery]]|volume=27|issue=2|url=http://research.microsoft.com/users/lamport/pubs/pubs.html#reaching|accessdate=2007-02-02}}</ref>。

合意プロトコルは分散コンピューティングにおける[[有限オートマトン|状態機械]]アプローチの基礎であり、これは[[レスリー・ランポート]]<ref name=clocks>
{{cite journal<!--|curly=yes-->|last=Lamport|first=Leslie|year=1978|month=July|title=Time, Clocks and the Ordering of Events in a Distributed System|journal=[[Communications of the ACM]]|volume=21|issue=7|pages=558--565|url=http://research.microsoft.com/users/lamport/pubs/pubs.html#time-clocks|accessdate=2007-02-02|doi=10.1145/359545.359563}}
</ref>により提案され、Fred Schneiderによってサーベイがなされている<ref name=ATutorial>
{{cite journal<!--|curly=yes-->|last=Schneider|first= Fred|year=1990| title=Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial|journal=ACM Computing Surveys|volume=22| url= https://web.archive.org/web/20060508040935/http://www.eecs.harvard.edu/cs262/DSbook.c7.pdf| doi=10.1145/98163.98167| pages=299}}
</ref>。

Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年であった<ref name=paxos>
{{cite journal<!--|curly=yes-->|last=Lamport|first=Leslie|year=1998|month=May|title=The Part-Time Parliament|journal=ACM Transactions on Computer Systems|volume=16|issue=2|pages=133--169|url=http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-paxos|accessdate=2007-02-02|doi=10.1145/279227.279229}}
</ref>。
これ以前に、[[ナンシー・リンチ]]、Cynthia Dwork、Larry Stockmeyerは"部分同期"システムの広い範囲における合意形成方法を[http://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf 例証している]。Paxosは分散トランザクションの文脈において、1988年にOkiとBarbara Liskovが発表したViewstampedレプリケーションにおける合意形成に使用されるプロトコルと非常に似ている<ref name=vr>
{{cite conference<!--|curly=yes-->|last=Oki|first=Brian|first2=Barbara |last2=Liskov|year=1988|title=Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems|book-title=PODC '88: Proceedings of the seventh annual [[ACM Symposium on Principles of Distributed Computing]]|pages=8--17|url=http://portal.acm.org/citation.cfm?id=62549|doi=10.1145/62546.62549}}</ref>。

'''状態機械アプローチ'''とはアルゴリズムをフォールトトレラントな、分散した実装に変換する技法である。アドホックな技術では重要な障害ケースが未解決
のままになる可能性がある。Lamport等によって定式化された手法では全てのケースが安全に処理されることを保証している。

Paxosプロトコル集合には次のものについてトレードオフを持っているような数種のものがある。
*プロセッサ数
*合意された値を知るまでのメッセージ遅延
*各ノードのアクティビティレベル
*送信されたメッセージ数
*障害の種類
Paxosプロトコル集合の共通の特徴は、不整合な状態に陥らないということがある<ref name="paxos"/><ref name=cheap>
{{cite conference<!--|curly=yes-->|last=Lamport|first=Leslie|first2=Mike |last2=Massa|year=2004|title=Cheap Paxos|book-title=Proceedings of the [[International Conference on Dependable Systems and Networks]] (DSN 2004)|url=http://research.microsoft.com/users/lamport/pubs/pubs.html#web-dsn-submission}}
</ref><ref name=fast>
{{cite web<!--|curly=yes-->|last=Lamport|first=Leslie|year=2005|accessdate=2007-02-02|title=Fast Paxos|url=http://research.microsoft.com/users/lamport/pubs/pubs.html#fast-paxos}}
</ref><ref name=general>
{{cite journal<!--|curly=yes-->|last=Lamport|first=Leslie|year=2005|accessdate=2007-02-02|title=Generalized Consensus and Paxos|url=http://research.microsoft.com/users/lamport/pubs/pubs.html#generalized}}
</ref><ref name=byzantine>
{{cite web<!--|curly=yes-->|last=Castro|first=Miguel|year=2001||accessdate=2007-02-02|title=Practical Byzantine Fault Tolerance|url=http://citeseer.ist.psu.edu/castro01practical.html}}
</ref>。

==安全性と活性に関する特性==

安全性を保証するため、Paxosは3つの安全性の特性を定義し、障害パターンによらず、これらが必ず守られていることを保証する。

;非自明性:提案された値のみが習得される。<ref name=fast/>
;完全性:最大一つの値が習得可能である。(つまり、2つの習得ノードがことなる値を習得することはない)<ref name=fast/><ref name=general/>
;活性(C;L):もし、値Cが提案されたならば、習得ノードLは何らかの値を習得する。(ただし十分数のプロセッサが障害を起こしていない場合)<ref name=general/>

==前提==

Paxosの説明を単純化するため、次の前提や定義が明確化されなければならない。応用範囲を広げるための技術は文献に提示されており、当記事では触れない。詳細は外部リンクを参照のこと。

===プロセッサ===
*プロセッサは任意の速度で動作してもよい。
*プロセッサは障害が発生する可能性がある。
*安定したストレージを持つプロセッサは障害の後、再参加可能である。
*プロセッサは共謀したり、誤った情報を返すなど、プロトコルの手続きを変えるようなことはしない。(任意の障害を容認する手法として、[[#ビザンチンPaxos]]を参照のこと)

===ネットワーク===

*プロセッサは他の全てのプロセッサにメッセージを送信することが可能である。
*メッセージは非同期的に送信され、到達までに任意の時間がかかることがある。
*メッセージは失われたり、順序を変更されたり、複製されることがある。
*メッセージは破損なしに配信される。(任意の障害を許容する手法として[[#ビザンチンPaxos]]を参照のこと)

===プロセッサ数===
一般に、分散合意アルゴリズムは<math>2F+1</math>個のプロセッサが存在すれば<math>F</math>個のプロセッサが同時に障害を起こした場合でも動作することができる。しかし、同時障害が<math>F</math>以下なら、再構成を行うことによって、合計の障害数がいくら増えてもよいようにプロトコルを作ることができる。

==役割==
Paxosはプロトコルにおけるプロセッサの動作を、クライアント(Client)，アクセプタ(Acceptor)，プロポーザ(Proposer)，ラーナ(Learner), リーダ(Leader)のいずれかの役割として表現する。
典型的な実装では、1つのプロセッサは同時に2つ以上の役割を演じることもできる。
これによってプロトコルの正当性に影響を受けることはない。
実際、プロトコルが必要とする遅延やメッセージ数を改善するために、複数の役割をまとめることはよく行われる。

; クライアント:
クライアントは分散システムに対してリクエストを送信し、返信を待つ。
分散ファイルサーバー上のファイルに対する書き込みリクエストはその1例である．

; アクセプタ:
アクセプタはフォールトトレラントな「メモリ」として働く。
アクセプタはクォーラム(Quorum = 定足数)と呼ばれるグループにまとめられる。
アクセプタへのメッセージは必ず定足数のアクセプタに送られなければならない。
アクセプタが受信したメッセージは、グループの各アクセプタから同じコピーが送られてこない限り無視される。

; プロポーザ:
プロポーザはクライアントのリクエストを支持して、アクセプタの同意を取ろうと試み、プロトコルを前に進めるための調停を行う。

; ラーナ:
ラーナはプロトコルの複製要素として働く。
一旦クライアントのリクエストがアクセプタによって同意されると、ラーナはアクションを取る(すなわち、クライアントのリクエストを実行しその結果をクライアントに返信する)ことができる。
可用性を高めるために、複数のラーナが存在しても良い。

; リーダ:
Paxosはリーダと呼ばれる特別なプロポーザが必要である。
複数のプロセッサが、自身がリーダであると信じることがあり得るが、そのどれかが最終的に選ばれる場合に限り、プロトコルは前進することが保証される。
もし2つのプロセッサがリーダーであると信じている場合、競合するアップデートを繰り返し提案することにより、プロトコルを停止させてしまうことがありえる。しかし、その場合でも安全性は保たれている。

===クォーラム===
クォーラムは、少なくとも一定以上のプロセッサが結果に関する知識を保持している事を保証することによって、Paxosの安全性を担保する。
クォーラムはアクセプタの集合の部分集合であって、どの二つの部分集合(つまりクォーラム)も1つ以上のメンバを共有しているものと定義される。
典型的には、クォーラムは過半数のアクセプタである。
例えば、4つのアクセプタ<math>\{A, B, C, D\}</math>が与えられた場合、過半数のクォーラムは任意の3つのアクセプタの集合({A, B, C}, {A, B, D}, {A, C, D}, {B, C, D})である。
一般の場合、アクセプタに任意の正の重みを割り当てて、メンバの重みの和が全体の重みの過半となるような集合がクォーラムである。

===提案番号と合意値===
合意結果（合意値）を v と定義する試みは、アクセプタに対する提案として行われる。
各提案はプロセッサによってユニークな番号が振られる。
番号が振られた提案に対する合意値は Paxos プロトコルを実行する過程で計算されても良いし，そうでなくてもかまわない。

==基本Paxos==

==ビザンチンPaxos==

== 脚注 ==
{{reflist}}

== 関連項目 ==
* [[有限オートマトン]]

== 外部リンク ==
* [http://www.lamport.org/ Leslie Lamport's home page]
* [http://research.microsoft.com/users/lamport/pubs/pubs.html#paxos-simple Paxos Made Simple]
* [http://citeseer.ist.psu.edu/deprisco97revisiting.html Revisiting the Paxos Algorithm]
* [http://research.microsoft.com/users/lamport/pubs/pubs.html#paxos-commit Paxos Commit]
* [http://pine.cs.yale.edu/pinewiki/Paxos Yale University's Wiki article]
* [http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-paxos Leslie Lamport's history of the paper]
* [http://labs.google.com/papers/chubby.html Google Whitepaper: Chubby Distributed Lock Service]
* [http://labs.google.com/papers/bigtable.html Google Whitepaper: Bigtable A Distributed Storage System for Structured Data]
* [http://brturn.googlepages.com/paxosfamily Survey of Paxos Algorithms (2007)]
* [http://scalien.com Keyspace, a consistently replicated open-source key-value store]

{{DEFAULTSORT:Paxosあるこりすむ}}
[[Category:分散アルゴリズム]]