分散アルゴリズム

論文翻訳: Paxos Made Simple

Takami Torao 2001年の論文 #Paxos
  • このエントリーをはてなブックマークに追加
Leslie Lamport
01 Nov 2001

Abstract

Paxos アルゴリズムは、わかりやすく説明するととてもシンプルである。

Table of Contents

  1. Abstract
  2. 1 はじめに
  3. 2 コンセンサスアルゴリズム
    1. 2.1 問題点
    2. 2.2 値の選択
    3. 2.3 選択された値の習得
    4. 2.4 進行
    5. 2.5 実装
  4. 3 ステートマシンの実装
  5. REFERENCES
  6. 翻訳抄

1 はじめに

フォールトトレラントな分散システムを実現する Paxos アルゴリズムは、オリジナルのプレゼンテーションがギリシャ語だったためか、多くの読者にとって理解することが難しいとされてきた [5]。しかし実際には分散アルゴリズムの中でも最も単純で分かりやすいものの一つである。その核心は [5] のコンセンサスアルゴリズム ── "教会会議" (synod) アルゴリズムである。次のセクションでは、我々が満たすべき性質からこのコンセンサスアルゴリズムがぼほ必然的に導かれることを示す。最後のセクションでは完全な Paxos アルゴリズムを説明する。このアルゴリズムは分散システムを構築するためのステートマシンアプローチに単純にコンセンサスを適用することで得られるものである ── このアプローチはおそらく分散システムの理論に関して最も頻繁に引用されている論文 [4] の主題であるためよく知られているはずである。

2 コンセンサスアルゴリズム

2.1 問題点

値を提案できるプロセスの集まりを想定する。コンセンサスアルゴリズムは、提案された値の中から一つの値が選ばれることを保証する。値が提案されていないのであれば、値は選択されるべきではない。値が選択された場合、プロセスはその値を知る (learn) ことができるべきである。コンセンサスの Safety 要件は:

  • 提案された値のみを選択できる。
  • 単一の値のみが選択される。
  • プロセスは、実際に選択されない限り、ある値が選択されたことを知ることはない。

ここでは正確な Liveness 要件を指定することはしない。しかし目標は、提案された値が最終的に選択され、値が選択された場合にはプロセスが最終的にその値を知ることができることを保証することである。

ここで、コンセンサスアルゴリズムにおける 3 つの役割を提案者 (proposer)、受諾者 (acceptor)、習得者 (learner) という 3 つの分類のエージェントに担わせる。実装では 1 つのプロセスが複数のエージェントとして動作することもあるが、エージェントからプロセスへのマッピングはここでは問題としない。

エージェントはメッセージを送信することで互いに通信できると仮定する。ここでは慣習的な非同期型の非ビザンチンモデルを使用している。

  • エージェントは任意の速度で動作し、停止して失敗することもあれば再起動することもある。すべてのエージェントがある値を選択した後に失敗し再起動する可能性があるため、失敗して再起動したエージェントは何らかの情報を記憶できなければ解決は吹かうである。
  • メッセージは届くまでに任意の時間がかかったり、重複したり、紛失することがあるが、破損することはない。

2.2 値の選択

値を選択する最も簡単な方法は 1 人の受諾者エージェントを置くことである。提案者は受諾者に提案を送り、受諾者は最初に受け取った提案値をを選択する。この解決策はシンプルだが、受諾者が故障するとそれ以上の進展が不可能となるため満足できるものではない。

では別の方法で値を選んでみよう。単一の受諾者の代わりに複数の受諾者エージェントを使用する。提案者は提案値を一連の受諾者に送る。受諾者は提案された値を受け入れる (accept) ことができる。十分な数の受諾者がその値を受け入れたとき、その値が選択される。十分な大きさとは何か? 単一の値のみが選択されるようにするには、十分に大きな集合を任意のエージェントの過半数で構成するようにすれば良い。任意の 2 つの過半数は、少なくとも 1 人の共通の受諾者を持っているため、受諾者が最大 1 つの値を受け入れることができればこの方法は有効である (過半数の明らかな一般化があり [3] から始まったと思われる多くの論文で観察されている)。

故障やメッセージの損失がない場合、1 人の提案者から 1 つの値しか提案されなくても 1 つの値が選択されるようにしたい。これは次の要件を示唆している:

\(P1\). 受諾者は最初に受け取った提案を受け入れなければならない。
An acceptor must accept the first proposal that it receives.

しかしこの要件には問題がある。異なる提案者によって複数の値がほぼ同時に提案され、すべての受諾者が値を受け入れたが、過半数の受諾者が受け入れた値は一つもない、という状況になる可能性がある。提案値が 2 つであっても、それぞれが約半数の受諾者に受け入れられていれば、1 人の受諾者の故障でどちらの値が選択されたかを知ることができなくなる。

\(P1\) と、過半数の受諾者が受け入れた場合にのみ値が選択されるという要件から、受諾者は複数の提案を受け入れることができなければならない。我々は、提案のそれぞれに (自然な) 番号を割り当てることで、受諾者が受け入れることのできる様々な提案を記録する。混乱を避けるため、異なる提案には異なる番号をつける必要がある。これをどのように実現するかは実装によるため、ここではその想定のみとする。値は、その値を持つ 1 つの提案が過半数の受諾者に受け入れられたときに選択される。このとき、その提案 (とその値) が選択されたと言う。

複数の提案を選ぶことができるが、選ばれたすべての提案が同じ値であることを保証する必要がある。提案番号への帰納法により保証すれば十分である:

\(P2\). 値 \(v\) を持つ提案が選ばれた場合、それより高い番号を持つ選ばれた提案はすべて値 \(v\) を持っている。
If a proposal with value \(v\) is chosen, then every higher-numbered proposal that is chosen has value \(v\).

数字は完全に順序付けられているため、条件 P2 は単一の値のみが選択されるという重要な Safety 特性を保証している。

提案が選択されるためには少なくとも 1 人の受諾者に受け入れられなければならない。つまり次を満たすことにより P2 を満たすことができる:

\(P2^a\). 値 \(v\) を持つ提案が選ばれた場合、それより高い番号を持つ任意の受諾者によって受け入れられた提案はすべて値 \(v\) を持っている。
If a proposal with value \(v\) is chosen, then every higher-numbered proposal accepted by any acceptor has value \(v\).

我々は、何らかの提案が選択されていることを保証するために \(P1\) を維持する。通信は非同期であるため、特定の受諾者 \(c\) が一度も提案を提案を受け取っていない状態で提案が選ばれる可能性がある。新しい提案者が "目を覚まし"、異なる値を持つより高い番号の提案を出したとする。\(P1\) では \(c\) がこの提案を受け入れる必要があり \(P2^a\) に違反する。\(P1\) と \(P2^a\) の両方を維持するには \(P2^a\) を次のように強化する必要がある。

\(P2^b\). 値 \(v\) を持つ提案が選ばれた場合、任意の提案者によって発行したより高い番号の提案はすべて値 \(v\) を持っている。
If a proposal with value \(v\) is chosen, then every higher-numbered proposal issued by any proposer has value \(v\).

提案は提案者が発行しなければ受諾者に受け入れられないため、\(P2^b\) は \(P2^a\) を意味し \(P1\) も意味する。

\(P2^b\) を満たす方法を見つけるために \(P2^b\) が成り立つことを証明する方法を考える。番号 \(m\) と値 \(v\) を持つ提案が選択されたと仮定し、番号 \(n \gt m\) で発行された提案も値 \(v\) であることを示す。我々は \(n\) に対する帰納法を使って証明を簡単にする。つまり \(m .. (n-1)\) の番号で発行されたすべての提案が値 \(v\) を持つという追加の仮定のもとで、提案番号 \(n\) が値 \(v\) を持つことを証明する。ここで \(i .. j\) は \(i\) から \(j\) までの数字の集合を表す。番号 \(m\) の提案が選ばれるためには、受諾者の過半数からなる集合 \(C\) のすべての受諾者がそれを受け入れるような \(C\) が存在しなければならない。これを帰納法の仮定と組み合わせると、\(m\) が選ばれるという仮説は次のようになる:

\(C\) のすべての受諾者は \(m .. (n-1)\) 内の番号を持つ提案を受け入れており、任意の受諾者が受け入れた \(m .. (n-1)\) 内の番号を持つすべての提案は値 \(v\) を持つ。

過半数の受諾者からなる任意の集合 \(S\) には、少なくとも 1 人の \(C\) のメンバーが含まれているため、次のように不変性が保たれていることを確認することで、番号 \(n\) の提案が値 \(v\) を持つと結論づけることができる:

\(P2^c\). 任意の \(v\) と \(n\) に対して、値 \(v\) と番号 \(n\) の提案が発行された場合、(a) \(S\) 内の受諾者が \(n\) 未満の番号の提案を受諾していない、または、(b) \(v\) が \(S\) 内の受諾者が受諾した \(n\) 未満の番号の提案の中で最も高い番号の提案の値である、のいずれかとなるような受諾者の過半数からなる集合 \(S\) が存在する。
For any \(v\) and \(n\), if a proposal with value \(v\) and number \(n\) is issued, then there is a set \(S\) consisting of a majority of acceptors such that either (a) no acceptor in \(S\) has accepted any proposal numbered less than \(n\), or (b) \(v\) is the value of the highest-numbered proposal among all proposals numbered less than \(n\) accepted by the acceptors in \(S\).

したがって \(P2^c\) の不変性を維持することで \(P2^b\) を満たすことができる。

\(B2^c\) の不変性を維持するには、番号 \(n\) の提案を発行しようとする提案者は、ある過半数受諾者のすべての受諾者に受け入れられた、または受け入れられるはずの、\(n\) 未満で最も大きい番号を持つ提案を知る必要がある。すでに受け入れられている提案を知ることは簡単だが、将来の受け入れを予測することは困難である。提案者は未来を予測する代わりに、そのような受諾がないことを約束させることでそれを制御する。言い換えると、提案者は受諾者に対して、\(n\) よりも小さい番号の提案をこれ以上受け入れないように要求する。このことから、提案を発行するためのアルゴリズムは次のようになる。

  1. 提案者は新しい提案番号 \(n\) を選択し、受諾者のある集合の全てのメンバーにリクエストを送信し、次を持つ応答を求める:
    1. \(n\) 未満の番号の提案を再び受け入れないという約束と、
    2. もしあれば受諾者が受け入れている \(n\) より小さく最も大きい番号の提案。
    このような要求を番号 \(n\) の準備 (prepare) リクエストと呼ぶ。
  2. 提案者が過半数の受諾者から要求に対するレスポンスを受け取った場合、提案者は番号 \(n\) と値 \(v\) の提案を発行することができる。\(v\) はレスポンスの中で最も高い番号の提案の値、または応答者が提案を報告しなかった場合は提案者が選択した任意の値である。

提案者は、ある受諾者の集合に提案を受け入れるようにリクエストを送ることで提案を発行する (これは初期リクエストに応答した受諾者の集合と同じである必要はない)。これを受入 (accept) リクエストとする。

これは提案者のアルゴリズムを説明したものである。では受諾者はどうだろうか? 受諾者は提案者から準備リクエストと受入リクエストの 2 種類の要求を受け取ることができる。受諾者は Safety を損なわずにどのような要求も無視することができる。そこで、どのような場合にリクエストに応答することが許されているかを示す必要がある。準備リクエストは常に応答できる。受入リクエストに対しては、受け入れしないと約束していなければ提案を受け入れて応答することができる。言い換えると:

\(P1^a\). 受諾者は、\(n\) より大きい番号を持つ準備リクエストに応答していなければ、番号 \(n\) の提案を受け入れることができる。
An acceptor can accept a proposal numbered \(n\) iff it has not responded to a prepare request having a number greater than \(n\).

\(P1^a\) が \(P1\) を包括することに注意。

これで、(一意な提案番号を想定して) 必要な Safety を満たす値を選択するための完全なアルゴリズムが完成した。最終的なアルゴリズムは 1 つの小さな最適化を行うことで得られる。

受諾者が番号 \(n\) の準備リクエストを受け取ったが、すでに番号 \(n\) より大きい準備リクエストに応答し、番号 \(n\) の新しい提案を受け入れないことを約束していたとする。そこで、受諾者はそのような準備リクエストを無視できるようにする。また、すでに受け入れた提案に対する準備リクエストも無視させる。

この最適化により、受諾者が記憶しておく必要があるのは、これまでに受け入れた最も高い番号の提案と、これまでに応答した最も大きい番号の準備リクエストだけとなる。失敗しても \(P2^c\) は不変でなければならないため、受諾者は失敗して再起動してもこの情報を憶えていなければならない。提案者は、同じ番号の提案を再度発行しようとしない限り、いつでも提案を放棄し、そのことをすべて忘れることができることに注意。

提案者と受諾者のアクションを合わせると、アルゴリズムは以下の 2 つのフェーズで動作することがわかる。

フェーズ 1

(a) 提案者は提案番号 \(n\) を選び、過半数の受諾者に番号 \(n\) で準備リクエストを送信する。

(b) 受諾者は、すでに自分が応答している準備リクエストより大きい番号 \(n\) を持つ準備リクエストを受け取ると、これ以降 \(n\) よりも小さい番号の提案を受け入れないことを約束し、これまでに受け入れた最も高い番号の提案を添えて (もしあれば) リクエストに応答する。

フェーズ 2

(a) 提案者が (番号 \(n\) の) 準備要求に対して過半数の受諾者から応答を得た場合、提案者はそれらの受諾者のそれぞれに番号 \(n\) の提案に値 \(v\) を受付リクエストを送信する。

(b) 受諾者は、番号 \(n\) の提案に対する受付リクエストを受け取った場合、\(n\) よりも高い番号の準備リクエストにすでに応答していなければ、その提案を受け入れる。

提案者は、それぞれの提案でアルゴリズムに従う限り、複数の提案を行うことができる。提案者はいつでもプロトコルの途中で提案を放棄することができる (提案に対するリクエストやレスポンスが、提案が放棄されてあからかなり後に目的地に到着することがあっても、正しさは維持される)。ある提案者がより高い番号の提案を発行しようとし始めた場合には、おそらく提案を放棄することが良い考えである。したがって、もし受諾者がより高い番号の準備リクエストをすでに受け取っていて準備または受付リクエスをと無視した場合、おそらく提案者に知らせるべきであり、提案者はその手違反を放棄すべきである。これはパフォーマンスの最適であって正しさには影響しない。

2.3 選択された値の習得

ある値が選択されたことを知るためには、習得者は提案が過半数の受諾者によって受け入れられたことを知る必要がある。明らかなアルゴリズムは、各受諾者が提案を受け入れるたびに、すべての習得者に提案を送って応答させることである。これにより、習得者は選択された値をすぐに知ることができるが、各受諾者がそれぞれの習得者に応答する必要があり、その数の受諾者の数と習得者の数の積に相当する。

非ビザンチン故障の仮定により、ある習得者が別の習得者からある値が受け入れられたことを簡単に知ることができる。受領者は、識別された (distinguished) 習得者への受け入れを返信し、識別された習得者が他の習得者に値が選択されたことを通知するようにすることができる。この方法では、すべての習得者が選択された値を知るために余計なラウンドが必要である。また、識別した習得者が故障する可能性があるため信頼性も低くなる。しかし、この方法では受諾者の数と習得者の数を足した数の返信だけが必要となる。

より一般的には、受領者はある識別された習得者の集合に受け入れを返信させ、各習得者はある値が選択されたときにすべての習得者に通知することができる。より多くの識別された習得者セットを使用すればより高い信頼性が得られるが、通信の複雑さが増す。

メッセージの損失により、習得者の知ることのできない値が選択される可能性がある。習得者は受領者に、どの提案を受け入れたかを尋ねることができるが、受領者が失敗すると、過半数が特定の提案を受け入れたかどうかを知ることができなくなる。その場合、習得者は新しい提案が選ばれたときに初めてどの値が選ばれたかを知ることになる。ある値が選ばれたかどうかを知る必要がある場合、習得者は上述のアルゴリズムを使って提案者に提案を出させることができる。

2.4 進行

提案番号の増えてゆく提案を 2 人の提案者がそれぞれ出し続け、そのどれもが選ばれないというシナリオを作ることは簡単である。提案者 \(p\) は提案番号 \(n_1\) でフェーズ 1 を完了し、別の提案者 \(q\) は提案番号 \(n_2 \gt n_1\) でフェーズ 1 を完了する。提案者 \(p\) の提案番号 \(n_1\) に対するフェーズ 2 の受入リクエストは、受諾者の全員が提案番号 \(n_2\) 未満の新しい提案を受け入れないと約束しているため無視される。そこで提案者 \(p\) は新しい提案番号 \(n_3 \gt n_2\) に対するフェーズ 1 を開始し完了させ、提案者 \(q\) の 2 回目のフェーズ 2 の受入リクエストを無視させる、といった具合である。

進行を保証するためには、識別された提案者が提案の発行を試みる唯一の人として選ばれなければならない。識別された提案者が大多数の受諾者とうまく通信することができず、すでに使用されている提案よりも大きな番号の提案を使用すれば、受け入れられた提案を発行することに成功する。識別された提案者がより高い提案番号のリクエストを知ったときに、提案を放棄し再試行することで、最終的には十分に高い提案番号を選択することになる。

システム (提案者、受諾者、通信ネットワーク) が十分に機能していれば、識別された提案者を一人選出することで Liveness を実現することができる。Fischer, Lynch, Patterson [1] の有名な成果は、提案者を選出するための信頼性の高いアルゴリズムは、ランダム性か実時間 (例えばタイムアウトなど) のいずれかを使用しなければならないことを示唆している。しかし選挙の成否にかかわらず Safety は確保されている。

2.5 実装

Paxos アルゴリズム [5] はプロセスのネットワークを想定している。この合意アルゴリズムでは、各プロセスが提案者、受諾者、習得者の役割を果たす。アルゴリズムはリーダーを選択し、リーダーは識別された提案者と識別された習得者の役割を果たす。Paxos のコンセンサスアルゴリズムは正確に上述のもので、リクエストとレスポンスは通常のメッセージとして送信される (応答メッセージには混乱を防ぐために対応する提案番号のタグが付けられる)。受領者が記憶しておかなければならない情報を保持するために、故障時にも保存される安定したストレージが使用される。受諾者は実際に応答を送信する前に、意図した応答を安定したストレージに記録する。

あとは、2 つの提案が同じ番号で発行されることがないことを保証するためのメカニズムを説明するだけである。異なる提案者は別々の番号セットから自分の番号を選ぶため、2 人の異なる提案者が同じ番号の提案を発行することはない。各提案者は、これまでに発行しようとした最も高い番号の提案を (安定した記憶装置に) 記憶しており、これまでに使用した提案よりも高い番号でフェーズ 1 を開始する。

3 ステートマシンの実装

分散システムを実装する簡単な方法は、中央サーバにコマンドを発行するクライアントの集合体として実装することである。サーバはクライアントのコマンドを特定の順序で実行する決定論的なステートマシンとして説明することができる。ステートマシンは現在の状態を持ち、コマンドを入力としてステップを実行し、出力と新しい状態を生成する。例えば、分散型銀行システムのクライアントは窓口であり、ステートマシンの状態はすべてのユーザの口座残高で構成されているかもしれない。引き出しは、口座の残高が引出し額より大きい場合にのみ、口座の残高を減少させるステートマシンコマンドを実行することで行われ、出力として旧残高と新残高が生成される。

1 つの中央サーバを使用する実装では、そのサーバが故障すれば失敗する。そこで、それぞれが独立してステートマシンを実装するサーバの集合体を使用することにした。ステートマシンは決定論的であるため、すべてのサーバが同じコマンドシーケンスを実行すると、すべてのサーバが同じシーケンスの状態と出力を生成する。コマンドを発行したクライアントはどのサーバが生成した出力も使用することができる。

すべてのサーバが同じステートマシンコマンドのシーケンスを実行することを保証するために、我々は Paxos コンセンサスアルゴリズムの個別のインスタンスのシーケンスを実装し、\(i\) 番目のインスタンスによって選択された値は、シーケンス内の \(i\) 番目のステートマシンコマンドである。各サーバはアルゴリズムの各インスタンスにおいてすべての役割 (提案者、受諾者、習得者) を演じる。今の所、サーバのセットは安定していると想定しているため、コンセンサスアルゴリズムのすべてのインスタンスは同じエージェントのセットを使用する。

通常の運用では 1 台のサーバがリーダーに選ばれ、コンセンサスアルゴリズムのすべてのインスタンスにおいて、識別された提案者 (提案を発行しようとする唯一のサーバ) として機能する。クライアントはリーダーにコマンドを送信し、リーダーは各コマンドがシーケンスのどこに現れるべきかを決定する。リーダーは、あるクライアントのコマンドが 135 番目のインスタンスの値となるべきだと判断した場合、コンセンサスアルゴリズムの 135 番目のインスタンスの値として選択させようとする。通常は成功するが、故障や、他のサーバが自分をリーダーだと信じていて 135 番目のコマンドが何であるべきかについて異なる考えを持っているために失敗するかもしれない。しかし、コンセンサスアルゴリズムでは最大で 1 つのコマンドが 135 番目のコマンドとして選択されることを保証する。

このアプローチの効率性の鍵となるのは Paxos のコンセンサスアルゴリズムにおいて提案される値がフェーズ 2 まで選択されないことである。前述のように提案者のアルゴリズムのフェーズ 1 が完了すると、選択される値が決定するか、提案者が自由に値を提案できるようになるかのどちらかとなる。

ここでは Paxos のステートマシン実装が通常の動作時にどのように機能するかについて説明する。後ほど何が問題になるかを説明する。ここでは、前任のリーダーが故障したばかりで、新しいリーダーが選ばれたときにどうなるかを考える (システムの起動は、まだコマンドが提案されていない特殊なケースである)。

新しいリーダーは、コンセンサスアルゴリズムのすべてのインスタンスの習得者であるため、すでに選択されているコマンドのほとんどを知っているはずである。新リーダーはコマンド 1～135, 138, 139 で選択された値を知っているとする (コマンドシーケンスでこのようなギャップがどのように発生するかについては後で説明する)。そして、インスタンス 135～137 と 130 より大きい全てのインスタンスのフェーズ 1 を実行する (これがどのように行われるかを以下で説明する)。これらの実行の結果、インスタンス 135 および 140 で提案される値が決定されているが、他のすべてのインスタンスでは提案された値が成約されないままであると仮定する。次にリーダーはインスタンス 135 と 140 に対してフェーズ 2 を実行し、それによってコマンド 135 と 140 を選択する。

リーダー、およびリーダーが知っているすべてのコマンドを習得した他のサーバはコマンド 1～135 を実行できるようになった。しかしコマンド 136 と 137 がまだ選択されていないため、コマンド 138～140 を実行することができない。リーダーは、クライアントから要求された次の 2 つのコマンドをコマンド 136 と 137 とすることができる。その代わりに、コマンド 136 と 137 として、状態を変更しない特別な "noop" コマンドを提案することで、すぐにギャプを埋める (これはコンセンサスアルゴリズムのインスタンス 136 と 137 のフェーズ 2 を実行することによって行われる)。これら 9 つの no-op コマンドが選択されるとコマンド 138～140 が実行可能になる。

これでコマンド 1～140 が選択された。リーダーはコンセンサスアルゴリズムの 140 を超えるすべてのインスタンスのフェーズ 1 も完了しており、これらのインスタンスのフェーズ 2 で任意の値を自由に提案できる。リーダーは、クライアントが要求する次のコマンドにコマンド番号 141 を割り当て、コンセンサスアルゴリズムのインスタンス 141 のフェーズ 2 の値として提案する。次に受信したクライアントのコマンドをコマンド 142 として提案し、以下同様に提案する。

リーダーは自分が提案したコマンド 141 が選択されたことを知る前にコマンド 142 を提案することができる。コマンド 141 の提案で送信したすべてのメッセージが失われ、リーダーがコマンド 141 として提案した内容を他のサーバが知る前にコマンド 142 が選択されてしまう可能性がある。リーダーは、インスタンス 141 のフェーズ 2 メッセージに対する期待される応答の受信に失敗すると、それらのメッセージを再送信する。すべてがうまくゆけばリーダーが提案したコマンドが選択される。ただし最初に失敗して、選択されたコマンドのシーケンスにギャップが生じる可能性もある。一般に、リーダーが \(\alpha\) 個のコマンドを先に取得できるとする。つまり、1 から \(i\) までのコマンドが選択され後に、\(i+1\) から \(i+\alpha\) までのコマンドを選択できるとする。その場合、最大で \(\alpha-1\) 個のコマンドのギャップが発生する可能性がある。

新しく選ばれたリーダーは、コンセンサスアルゴリズムの無限の数のインスタンス (上記のシナリオでは 135～137 と 139 より大きい全て) に対してフェーズ 1 を実行する。すべてのインスタンスに同じ提案番号を使用し、他のサーバに適度に短いメッセージを送信することでこれを行うことができる。フェーズ 1 では、受諾者はある提案者からフェーズ 2 のメッセージをすでに受け取っている場合にのみ、単純な OK 以上の応答をする (シナリオでは、これはインスタンス 135 と 140 のみが該当した)。したがって (受諾者として機能する) サーバは、単一の適度に短いメッセージですべてのインスタンスに応答できる。このため、これらの無限に多いフェーズ 1 のインスタンスを実行しても問題はない。

リーダーの故障と新しいリーダーの選出はまれな出来事であるはずなので、ステートマシンのコマンドを実行するための効果的なコスト、つまりコマンド/値のコンセンサスを達成するためのコストは、コンセンサスアルゴリズムのフェーズ 2 のみを実行するコストである。Paxos のコンセンサスアルゴリズムのフェーズ 2 は、障害がある場合に合意に達するためのアルゴリズムの中で、可能な限り最小のコストであることが示されている [2]。したがって Paxos アルゴリズムは本質的に最適である。

システムの通常運用に関して、現在のリーダーが故障してから新しいリーダーが選出されるまでの短い期間を除いて常に 1 人のリーダーが存在することを前提に説明する。異常な状態ではリーダー選出が失敗することもある。リーダーとして機能しているサーバが存在しない場合は新しいコマンドが提案されない。複数のサーバが自身がリーダーと考えている場合、それらはコンセンサスアルゴリズムの同じインスタンスですべての値を提案することができ、それによってどの値も選択されなくなる可能性がある。ただし安全性は維持されており、2 つの異なるサーバが \(i\) 番目のステートマシンコマンドとして選択された値について意見が相違することはない。1 人のリーダーを選出する必要があるのは進行を確実にするためだけである。

サーバ構成が変更可能であるならば、コンセンサスアルゴリズムのどのインスタンスをどのサーバが実装しているかを判断する方法が必要である。これを行う最も簡単な方法はステートマシン自体を使用することである。現在のサーバ構成を状態の一部にして、通常のステートマシンのコマンドで変更することができる。コンセンサスアルゴリズムのインスタンス \(i+\alpha\) を実行するサーバのセットを \(i\) 番目のステートマシンコマンド実行後の状態で指定することにより、リーダーが \(\alpha\) 個のコマンドを先に取得できるようにすることができる。これにより任意の洗練された再構成アルゴリズムを簡単に実装することができる。

REFERENCES

  1. Michael J. Fischer, Nancy Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, April 1985.
  2. Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus when there are no faults—a tutorial. TechnicalReport MIT-LCS-TR-821, Laboratory for Computer Science, Massachusetts Institute Technology, Cambridge, MA, 02139, May 2001. also published in SIGACT News 32(2) (June 2001).
  3. Leslie Lamport. The implementation of reliable distributed multiprocess systems. Computer Networks, 2:95–114, 1978.
  4. Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, July 1978.
  5. Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133–169, May 1998. (日本語訳)

翻訳抄

Paxos に関する 2001 年の論文。独特のユーモラスにより世間にうまく伝わらなかった先の論文 "The part-time parliament" [5] をサマリーしたような内容となっている。

  1. LAMPORT, Leslie. Paxos made simple. ACM Sigact News, 2001, 32.4: 18-25.