paxos需要滿足的條件：
- 多個提案中只能有一個被接受。
- 被接受的這個提案最終需要讓所有的參與者都知道。
paxos中的三個角色：
- proposers 提議者
- acceptors 決策者
- learners 被通知者
參與者之間的通訊模型：
- 各個參與者之間都可以通訊
- 通訊是異步的，不保證順序
- 通訊質量不保證，消息可以丟失，重發
- 參與者可以宕機再重啟
- 所有參與者都不能偽造消息
如何從多個提案中唯一的選定一個？
- 前置條件P1：為了保證在只有一個提案的情況下這個提案能夠被接受，每個決策者必須接受他收到的第一個提案。
- 提案被選定的標準：這個提案被多數派接受。
- 根據P1和提案被選定的標準可以推導出：每個決策者必須能夠接受多個提案（>=1）。（如果只能接受收到的第一個提案，會有很多情況無法選定最終的提案）
- 基於以上原因，每個決策者必須可以接受多個提案。每個提案id唯一。
- 條件P2：If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.
- 條件P2b：If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.
- 只有能滿足P2b 肯定可以滿足P2。
經過證明只要滿足如下的協議就可以滿足P2b：
- 對於提議者需要滿足如下協議： a) 第一個階段，發送prepare request，其中包含了提案號n。接收者會把自己已經接收的提案號小於n的最大的提案號發送給提議者，並保證不會在接受小於編號n的提案； b）第二階段提議者發送accept request，其中提案號為n，value 為a）中接收到的最大提案號的值，如果沒有則隨意設置值。
- 對於決策者需要滿足如下協議： 他可以接受提案號為n的提案，如果他沒有回覆過提案號大於n的prepare request的話。
最終的協議(2階段協議)：
- Phase 1 ： a）提議者發送編號為n的prepare request給多數派； b）接受者如果沒有收到過比n大的prepare request，他會回覆自己已經接受的最大的提案好，並承諾不再接收編號更大的提案。
- Phase 2: 當提議者收到多數派的回覆後，發送accept request，提案編號為n，值是phase1中收到的回覆中最大的提案的value。決策者如果沒有回覆提案號大於n的話，決策者可以接受這個提案。
如何知道一個提案被選定了？
- 當多數派接受了accept request之後，這個提案就被選定了。
分享到:
閱讀更多 十萬個為神麼 的文章
