Paxos協議

02-04

Paxos是由Leslie Lamport發明的分散式一致性演算法，1989年發布的The Part-Time Parliament論文發布後，很多人高呼看不懂，所以在2001年，Leslie Lamport又發表了這篇Paxos Made Simple。從標題就可以看出來，對大眾充滿了深深的鄙視。

文章中提到了distinguished Proposer 和 distinguished Learner，還有timeouts
允許leader發完commands1，3後掛掉，即允許gap
Raft是Paxos的實現

Vn = last of (Va,Vb,Vc)

從上圖中可以看到，Paxos系統有三個角色：Proposer, Acceptor, Learner。

Proposer向Acceptor拉票，帶上自己的proposal號n。Acceptor如果確認當前收到的請求裡面的proposal號n是目前收到最高的，就回答把票給你。Proposer確認獲得過半票後，通知Acceptor自己的選舉成功。Acceptor通知Proposer和Learner選舉結果。Learner返回結果給Client。

Acceptor或Learner掛了怎麼辦？

不影響過程。

Proposer掛了怎麼辦？

重新選舉。

多個Proposer？

這裡可能造成活鎖，兩個Proposer不斷增加proposal號，導致之前proposer的選舉失敗。所以提出了multi-paxos的解決方案：一次只有一個proposer。即引入leader的概念。

為什麼有些地方稱為multi-paxos？

表示有leader，不用每次都經歷第一階段（下面的Phase 1）。Multiple rounds of the algo to agree sequential requests from a stable leader with minimal messaging.

Paxos演算法論文原文的表述如下：

Phase 1:

(a) A proposer selects a proposal number n and sends a prepare

request with number n to a majority of acceptors.

(b) If an acceptor receives a prepare request with number n greater

than that of any prepare request to which it has already responded,

then it responds to the request with a promise not to accept any more

proposals numbered less than n and with the highest-numbered pro-

posal (if any) that it has accepted.

Phase 2:

(a) If the proposer receives a response to its prepare requests

(numbered n) from a majority of acceptors, then it sends an accept

request to each of those acceptors for a proposal numbered n with a

value v, where v is the value of the highest-numbered proposal among
the responses, or is any value if the responses reported no proposals.

(b) If an acceptor receives an accept request for a proposal numbered

n, it accepts the proposal unless it has already responded to a prepare

request having a number greater than n.

Reference: Paxos Made Simple