論文メモ Paxos Made Simple

December 31, 2020

The Part-Time Parliamentで提唱された分散含意アルゴリズムPaxosをLamport自身が平易に解説した。 エージェントの処理速度やメッセージが配信されるまでの長さに仮定はない。 メッセージは複製、喪失してもよい。 他方で、ビザンチン将軍問題は扱わず、メッセージが壊れることは考えない。

proposer, acceptor, learnerの3種類のエージェントがあり、proposerに提案された値の中から、ただ一つの値が選ばれることが保証される。 プロセスは複数のエージェントの役割を兼ねてもいい。 proposalには全順序の番号proposal number \(n\)が与えられ、任意のproposalに順序をつけることができる。 値の選出のためにproposerからacceptorに送るリクエストはprepare request, accept requestの2種類で、それぞれ第1, 第2フェーズで送られる。

第1フェーズでは、はじめに、proposerはproposal number \(n\)を選び、\(n\)のついたprepare requestを過半数のacceptorに送る。 acceptorは、これまでに応答したどんなproposal numberよりも大きな\(n\)のprepare requestを受信したら、以降は\(n\)未満のproposalをacceptするのを止め、また、もしあるならacceptずみのproposalで最大の番号のproposalをproposerに返す。

第2フェーズでは、proposerが過半数のacceptorから\(n\)のprepare requestの応答を受信したら、\(n\)のproposalに対するaccept reqestを値\(v\)をつけてacceptorに送る。 \(v\)は第1フェーズでacceptorから返されたresponseの中で最大の番号の値、ただし、responseがないときは任意の値でいい。 もしacceptorが\(n\)のaccept requstを受信したら、\(n\)より大きなprepareリクエストに応答していない限り、requestを受理する。

複数のproposerによるフェーズ1が重なると、フェーズ2に進まず、含意に到達できないことがある。 Paxosの進行を保証するには、proposerの数を制限したり、タイムアウトやランダム性でproposerのふるまいを制限したりする必要がある。

acceptorは値を受理したことをlearnerに伝達する。 acceptorはdistinguish learnerに受理したproposalを伝達し、distinguish leanerは他のlearnerにproposalを伝達する。 distinguish learnerを増やすほど伝達の計算量は増えるが、信頼性を上げることができる。


論文をこちらからダウンロードできます。