# 書誌情報 - **タイトル**: Paxos Made Simple - **著者**: [[Leslie Lamport]] - **出版年**: 2001 - **ジャーナル・カンファレンス**: N/A - **Abstract**: The Paxos algorithm, when presented in plain English, is very simple. # PDF ![[paxos-simple.pdf]] # 2. The Consensus Algorithm ## 2.1 The Problem - コンセンサス問題の定式化がされている - [[Validity]]: 提案された値のみが決定値に選ばれる - [[Agreement]]: 単一の値のみが決定される - 実際に決定されるまで、プロセスは決定値を見ない（これもAgreement?） - [[Termination]]: 最終的に提案された値が選択され、各プロセスが決定値を見れる - **Proposer, Accepter, Learner**の3者がいる - システムモデル - [[Byzantine Fault]]は仮定しない。[[Crash-recovery model]]。 - [[Asynchronous System]] - [[ネットワークのシステムモデル|Network Model]]: [[Fair-loss link]] # 2.2 Choosing a Value - Accepterが単一だったら、無問題 - でも、故障したら[[Progress]]（[[Liveness]]）を保証できない - Accepterが複数いれば、故障に耐えられる > [!abstract] Requirements > 過半数のAccepterに受け入れられれば（2f+1）、それが決定値となる - 1つのProposerしか値を提案しなかったとしても、その値が選ばれる（chosen）ようにしたい - P1がないと、Proposerが1つしかいなかったら、いつまでも進行しない > [!summary] Requirements > P1: An acceptor must accept the first proposal that it receives > （各Acceptorは、最初に受け取った提案をAcceptしなければいけない） - P1では不十分。複数の提案者が異なる値を提案して、全てのAcceptorが異なる値をAcceptして、どの値も過半数に達していないという状況があり得る - 2つしか提案値がなかったとしても、1つ故障していたら過半数に達しないケースがありうる - [[Split Vote]]の問題を言ってる - P1 かつ 過半数のAcceptorがAcceptしたらChooseされるという要件は、Acceptorが1つ以上の提案を受け入れることを許さねばならないということを意味する - 最初は論理の飛躍だと思ったけど。。。 - P1だけでは、split voteが発生したときに「誰も過半数を得られない状況」から抜け出せない→過半数の要求を満たすため、acceptorが複数の提案を受け入れられるようにすれば、いつかは過半数の状況にたどり着くってこと? それをP2以降で保証していくぜってこと?（要確認） - というわけで、複数のProposalがchooseされることもできるが、その場合それぞれchooseされた値は同じにならないといけないとすればOK - 各Proposalには自然数の提案番号を付けることとする > [!summary] Proposition > P2: If a proposal with value $v$ is chosen, then every higher-numbered proposal that is chosen has value $v$. > （値$v$のProposalがchooseされたら、全ての後のchooseされたproposalの値は$v$） - P2は、[[Agreement]]を保証するための要件。 - 以下のP2aを満たすことで、P2を満たせる > [!abstract] Proposition > P2a: If a proposal with value $v$ is chosen, then every higher-numbered proposal **accepted** by any acceptor has value $v$. > （値$v$のProposalがchooseされたら、全ての**accept**されたproposalの値は$v$） - ここまで、P1、P2a両方必要になっている - しかし、accepter cがまだ提案を受け取っていないとして、寝ていたproposerが起き上がり、別の値の提案をcに送りつけたら、P1のルールに従っていてはP2aに違反してしまう - ということで、P2bを保証する必要がある > [!abstract] Proposition > P2b: If a proposal with value $v$ is chosen, then every higher-numbered proposal issued by any proposer has value $v$. > （値$v$のProposalがchooseされたら、全てのそれ以降のproposalの値は$v$となる） - そもそも、全部のproposalが$v$になれば、P1とP2を両方満たせるよね - P2bはP2aを満たし、P2aはP2を満たす。 - ここまでまとめると、P1とP2bを満たせばOKということになる。 安全性の証明（P2） いくつかのProposal (m, v)が選ばれた（chosen）と仮定した場合、n > mな任意のproposalの値がvとなるには、どうすればいいのか? 安全性証明をパスする方法（仮説）は、以下だ。 [[数学的帰納法]]を使う。nが値vを持つことを、帰納法の仮定「m..(n-1)の全てのproposalが値vをもつ」の仮定から導く。 - 番号mの提案が選ばれたということは、、、 - 番号$m$の仮定が選ばれるためには、Acceptorの集合のうち過半数のAcceptorを含む集合$C$からacceptされていないといけない。 - 以降、$C$のacceptorはmより大きい番号の提案をacceptするとき、必ず$v$を使う←方法（仮説） - 番号nの提案が発行されたら - Proposerは、acceptorの過半数から過去にacceptした最大番号の値を集める←方法（仮説） - Cのacceptorは、m..n-1の番号の提案をacceptしているので、必ずvを返す - Proposerは、vを新しい提案値として使う - Proposal (n, v)は過半数のacceptorにされる - Acceptorの過半数が属する任意の集合$S$は、必ず$C$のメンバを1つは含む（2f+1だから） というわけで、方法（仮説）と書いた部分をプロトコルに組み込もう（P2c）。 > [!summary] Proposition > P2c: 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$. P2cって、real timeで知れれば、ってこと? 下の方で触れられているプロトコルはそれを満たしてる?（要確認） P2cの不変性を保証することで、P2bを満たすことができる。 ## Paxos Algorithm ここからが本題。今までの説明の要件を満たすプロトコルを提案。 1. Prepare Request: Proposerは新しい提案番号$n$を選択し、Acceptorsに*Prepare*リクエストを送り、応答を待つ - $n$未満の番号の提案を二度と受け入れないように約束してもらう - $n$より小さく、かつ最大値の提案番号を持つ提案値があれば、それを教えて下さい 2. Accept Request: Proposerが過半数のAcceptorから応答を受け取った場合、提案者は(n, v)のProposalを送る - v: 応答の中で一番提案番号が大きいproposalの値（なにも報告がなければProposerが決める任意の値） - Acceptorは、nより大きいPrepare Requestに応答していない限り、Acceptする > [!summary] Proposition > P1a: An acceptor can accept a proposal numbered $n$ iff it has not responded to a prepare request having a number greater than $n$. > （Acceptorは、nより大きいPrepare Requestに応答していないときのみ、Proposalをacceptできる） P1aはP1を内包する。 ここまでで[[Safety]]を満たすアルゴリズムができた 以下最適化 - すでにnより大きいPrepare Requestに応答していたら、nのPrepare Requestには応答しない # 2.3 Learning a Chosen Value - 過半数のAcceptorに受け入れられたことを、Learnerはどうやって知るか? - 自明な解決策: AcceptorはAcceptするたびに、各LearnerにAcceptしたProposalを送る→過半数のAcceptorからvが得られたら終了 - でもこれって、f+1のみAcceptして、その後1つ死亡したら、Livenessなさそうな? - でもメッセージ数が$O(N^2)$ - 他の解決策: AcceptorはDistinguished Learnerを選び、そいつにだけ伝える。Distinguished Learnerは、他のLearnerに教える - メッセージ数がacceptor数+learner数になる - これって、過半数超えたタイミングでLearnerに伝えるってこと?（要確認） - 毎回伝えてたらacceptor数 * learner数だよね? - でもこいつが故障したらおしまい - 一般化した解決策: 複数のDistinguished Learnerを使う # 2.4 Progress - Proposerが2ついて、Acceptorが1台故障している場合に、いつまでも進行しないシナリオがある - Proposerを1台に絞る（Distinguished Proposer）必要がある。 - Distinguished Proposerを選び出す仕組みはここでは触れていない - そんな[[FLP Impossibility|FLP]]に違反してAsynchronous環境でリーダー選挙できる仕組みある? って思ったが、Paxos自体のLivenessを保証するにはいつか1台だけ選べる（2台リーダーが生まれてもいい）アルゴリズムで十分じゃね? と思うと、いい話だ