# Paxos

## kumagi さんの解説

> Paxosアルゴリズムとは「ただ一つの覆らない値を選択する」アルゴリズム
>
> 複数のProposer(1,2,...k)が思い思いの値(v1,v2,...vk)と提案番号(n1,n2,...nk)を持ち寄り、Acceptorのクラスタの中でv1,v2,...vkのどれかの値を選択することに合意することを目標にしている。選択された値は二度と覆ることはない。

### 現時点での疑問
prepare と propose で何をしているか分からない...
Proposer（複数） と Accepter(複数) が登場人物として出てくることは分かった

https://qiita.com/kumagi/items/535c9b7a761d2ed52bc0

## 久保田さんの解説

https://www.slideshare.net/pfi/paxos-13615514

命令の列を全てのレプリカに同じ順序で届ける
- i 番目の命令として何を採用するかに対して合意を取る
- 全ての i に対して合意を取る
- 分散システムで合意を取るのは難しい
- 誰が取り仕切るか決まってない
- 返事が返ってこないこともある
- 仕切り役が二人以上いることもある
- 合意が必要なところ
- 分散トランザクション
- メンバシップ管理
- リーダー決定

FLP impossibility
「非同期システムでは、たとえメッセージのロスがなくとも、プロセスが一台でも停止する可能性がある限り、合意を取れるアルゴリズムは存在しない」
https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf

Paxos における制約
- P1: Accepter は最初に受け取った値を受理しなければならない
- P2: 一度値vを持つ提案が選択されたら、より大きな提案IDを持つ提案が選択される場合、その提案の値はvでなければならない
- P2a: 値vを持つ提案が選択されたら、任意のAccepterに受理される、より大きな提案IDを持つ提案の値はvでなければならない
- P2b: 値vを持つ提案が選択されたら、任意のProposerから提案される、より大きな提案IDを持つ提案の値はvでなければならない
- P2c: 値vを持つIDがnの提案がProposerより出た場合、次のようなAccepterの集合Sが存在しなければならない
- S には過半数の accepter が含まれる
- S に含まれるどの accepter もまだIDが n 未満の提案を受理していない (Proposerが好きな値を提案できる状態)
- S に含まれる accepter が受理したIDが n 未満の提案のうち、一番大きなIDを持つ提案の値はvである

現時点での問題
- 確認した時点での最大の提案IDは m
- ID = n > m で提案を行ったが、その途中で提案ID m' > n の提案が割り込み、その値が自分と違う値を持っている場合
- しかも m' が受理されてしまった場合
- これは P2c に反する
- 既に受理された提案IDより低い提案IDで別の値の提案をしてしまっているため

Prepare & Promise
- 自分の提案IDが提案時点で最大であることを保証したい
- 確認時点ではなくて提案時点
- Prepare(n) メッセージの導入
- 提案ID n 未満の提案は全て無視するように要請する
- 少なくとも自分より小さいIDの提案を無視させることができる
- Promise
- Accepter による Prepare に対する返信、受理するか拒否するか

自分の提案IDを提案時点で最大であると保証するためというより、最大でない場合に拒否してもらうことを保証させるための仕組みかな...?その裏返しで、受理される時はそのフィルターを通っているので最大の提案IDであると言える

Accept
- Prepare(n)のレスポンスを過半数から受け取ったら提案を送る
- P2c に従って値を提案
- Accept(n, v)
- n は prepare した提案ID
- v は提案する値
- Accepter はどう対応するべきか
- n より大きなIDで prepare されていたら提案を拒否
- prepare されていたIDの場合は受理し Accepted メッセージを返信
- Accept で渡されたIDが prepare されているIDより大きい場合でも accept する
- 自分以外の過半数の accepter がそのIDで prepare されているはずであるため、元々 prepare されていた古い提案 ID による提案が通ることはないため、影響はない

制約まとめ
- P1: Accepter は最初に受け取った値を受理しなければならない
- P1a: Accepter は n より大きな Prepare リクエストを受理していないとき、またそのときに限りIDが n の提案を受理できる
- P2: 一度値vを持つ提案が選択されたら、より大きな提案IDを持つ提案が選択される場合、その提案の値はvでなければならない
- P2c: 値vを持つIDがnの提案がProposerより出た場合、次のようなAccepterの集合Sが存在しなければならない
- S には過半数の accepter が含まれる
- S に含まれるどの accepter もまだIDが n 未満の提案を受理していない (Proposerが好きな値を提案できる状態)
- S に含まれる accepter が受理したIDが n 未満の提案のうち、一番大きなIDを持つ提案の値はvである

Paxos
- フェーズ1: Prepare & Promise
- フェーズ2: Accept & Accepted

proposer のリーダーを選出する方法がある、split brain になっても paxos は大丈夫

learner がいい感じに頑張る
- 提案が選択されたことの確認
- 過半数の accepter に提案が accept されたことを確認する

Paxos の最適化
- 1回の合意形成に必要なメッセージ数が多い
- 最小4回
- Prepare
- Promise
- Accept
- Accepted
- Paxos のメッセージ数を減らしたい
- Cheap Paxos
- Fast Paxos
- Multi Paxos

Multi Paxos
- distinguished proposer が割と stable であると仮定
- 何回も連続でインスタンスを実行する場合
- 1回目に Prepare & Promise で Accept までたどり着いた
- 2回目は Prepare & Promise を省略できないか
- 前回のインスタンスとProposerが同じ場合はいきなり Accept に飛ばしていいんじゃない？
- 途中で他の proposer が prepare で割り込めるし、安全！

### 現時点での疑問
paxos を使うと分散システムでも一つの値を選ぶことに合意をとれることが分かった。
prepare メッセージの意味も分かった。
2回目以降の合意でも同じ値についてのみ必ず合意がとられることが分かった。
ただ、2回目以降の合意で同じ値について合意を取ることに何か意味があるのかどうか分からない。覆らないということは何か応用できそうではあるが...