【パクソス】
Paxos とは？
最終更新:
💡 提案番号と過半数で、決定の食い違いを防ぐ
分散システムで、提案された値のうち一つに合意するためのアルゴリズム。提案番号と過半数の応答を使い、一部の停止や通信遅延があっても、異なる値を確定しないようにする。
📌 このページのポイント
- 基本の合意では、提案された値のうち一つを選ぶ
- 提案者・受理者・学習者という役割を使い、一つのプロセスが兼ねることもある
- 準備で過去の受理を確認し、その結果を守って値を提案する
- 合意の安全性と、処理が進むための通信・提案者の条件を区別する
ひよこ 分散システムで何を決めるの？
ペンギン先生 基本の合意では、複数の提案から一つの値を選ぶよ。同じ決定について、別々の値が確定する食い違いを防ぐんだ。
ひよこ 単に多数決を取るだけ？
ペンギン先生 それだけではないよ。まず重複しない提案番号を送り、受理者から「より小さい番号の提案は今後受理しない」という約束と、過去に受理した提案を集める。過半数から応答を得て、次に出す値を決めるんだ。
ひよこ 前の提案があったら？
ペンギン先生 応答に過去の受理があれば、その中で最も大きな提案番号の値を引き継ぐよ。なければ新しい値を選べる。その値と番号を送り、過半数が受理すると値が選ばれるんだ。
ひよこ 3種類の役割は3台のサーバー？
ペンギン先生 提案者が提案し、受理者が約束や受理を記録し、学習者が選ばれた値を知る役割だよ。一つのプロセスが複数の役割を兼ねることもある。図は受理者3つのうち2つで過半数になる例だよ。
ひよこ 1つ止まっても必ず進む？
ペンギン先生 残る過半数と通信できることに加え、提案者同士が競合し続けないなどの条件が必要だよ。正しく実装して食い違う決定を防ぐことと、必ず進むことは別なんだ。基本形は停止などを想定し、参加者が嘘の情報を送る故障まで扱うものではないよ。
まとめ：ざっくりこれだけ覚えればOK！
「Paxos」って出てきたら「一部が止まっても、分散した参加者の決定が食い違わないようにする合意の仕組み」と思えばだいたいOK！
📖 おまけ：英語の意味
「Paxos」 ＝ 論文に登場する島の名前
💬 Leslie Lamportの「The Part-Time Parliament」は、Paxosという島の議会を題材に合意を説明しているよ。実在のギリシャの島の議会史として読む話ではないんだ。