Paxos Algorithm

最近上 operating systems, distributed systems 的課看了一些論文，

發現網路上中文資料相對英文還是少了一點，

所以想嘗試以初學者的角度解釋一些概念。


Paxos Algorithm 通常用在容錯分布式系統 (fault-tolerant distributed systems) 用來實現 Consensus Algorithm.

先來討論一下為什麼需要分布式系統。

假設你是一家銀行，擁有帳戶和餘額。

a. 今天我去領錢，機器當機了

1. 如果只有一個主機存資料，
-> 所有帳戶餘額會不正確

2. 如果有多個主機
-> 根據沒有當機的主機，recovery


b. 但是如果有多個主機，

餘額減少的那個主機，

如何更新餘額給其他主機知道就是 Paxos algo 討論的問題


核心概念：

每個process(node) 有 proposer, acceptor, learner.

proposer 送request 給其他 acceptors. (acceptors 有可能會收到多個)
prepare_request(n)

acceptors 會選收到最高的 n 的傳回去proposer
response_to_prepare_request(Proposal[m, w]/None)

proposer 根據 response 選出 MAJORITY 之後傳給其他 acceptor
accept_request(proposal[n,v])

acceptor 傳給其他 learner
decision(proposal[n,v])

learner 把收到的value寫到系統裡。

最終全部的process 都會有更新過的value.


這些步驟裡面有寫可以簡化，因此 paxos 還有其他的變種算法。


references:

https://www.youtube.com/watch?v=UUQ8xYWR4do
http://lamport.azurewebsites.net/pubs/paxos-simple.pdf