Paxos 알고리즘, 사실은 가장 단순한 분산 합의 알고리즘

Paxos Made Simple (2001)[pdf]

Leslie Lamport는 Paxos 알고리즘이 분산 시스템을 위한 내결함성 합의를 구현하는 데 어렵게 여겨져 왔지만, 사실은 가장 단순하고 명백한 분산 알고리즘 중 하나라고 설명한다. 이 논문은 합의 알고리즘의 핵심을 평이한 영어로 풀어내며, 제안자(proposer), 수락자(acceptor), 학습자(learner)의 역할과 안전성 요구사항을 단계적으로 유도한다. 또한 합의를 상태 머신에 적용하여 전체 Paxos 알고리즘을 구성하는 방법을 보여준다.