Paxosアルゴリズムとは？

Paxosアルゴリズムは、1980年代後半にLeslie Lamportによって考案された分散コンセンサスプロトコルです。複数のノード（サーバー）からなる分散システムにおいて、一部のノードが故障したり通信が遅延・欠落したりしても、残りのノードが同一の値に合意できることを保証します。

アルゴリズムは主に3つの役割に分類されます。

• Proposer（提案者）：合意を得たい値を提案するノード
• Acceptor（承認者）：提案を受け取り、承認するノード
• Learner（学習者）：決定した値を学習・適用するノード

合意の流れはフェーズ1（Prepare/Promise）とフェーズ2（Accept/Accepted）の2段階で進みます。Proposerがまず「準備」リクエストを送り、過半数のAcceptorから返答を得た後、「受け入れ」リクエストを送信します。過半数が受け入れたとき、その値が「決定値」となります。

Paxosの最大の特徴は、過半数ノードが稼働している限り安全性（Safety）と可用性（Liveness）を両立できる点です。ただし、アルゴリズムが複雑で実装が難しいため、実用上はMulti-PaxosやRaftなど簡略化・改良されたプロトコルが多く採用されています。Google SpannerやApache ZooKeeperの設計にもPaxosの思想が活かされています。