Paxosアルゴリズムを平易な英語で解説——Lamport自身による『Paxos Made Simple』

Paxos Made Simple (2001)[pdf]

分散システムにおける合意形成アルゴリズム「Paxos」は、難解とされてきたが、著者のLeslie Lamportは本稿で「平易な英語で書けば非常にシンプル」と述べ、アルゴリズムの本質を明確に解説する。プロセスが値を提案し、過半数のアクセプタが受理することで値が選択される仕組みを、安全性と進行性の要件から自然に導き出す。さらに、分散システム構築の一般的な手法であるステートマシンアプローチへの応用も示す。