Paxos 알고리즘은 분산 시스템에서 여러 프로세스가 하나의 값을 합의하도록 하는 합의(Consensus) 문제를 해결하는 대표적인 알고리즘입니다.

이 알고리즘은 Proposer, Acceptor, Learner 세 역할로 구성되며, 두 단계(Phase 1: 임시 리더십 확보, Phase 2: 값 승인)를 통해 다수의 동의를 얻어 결정을 내립니다.

FLP 불가능성 정리로 완전 비동기 환경에서 합의가 불가능함이 증명되었으나, Paxos는 부분 동기 환경을 가정하여 안전성(안전 속성)을 보장하면서도 실용적으로 합의를 이끌어냅니다.

또한, 제안 번호를 고유하고 증가하는 값으로 관리하고, 실패 시 랜덤 백오프를 적용해 리더 경쟁 문제를 완화합니다.

이 글은 단일 값 합의를 다루는 기본 Paxos를 쉽게 설명하며, 확장된 Multi-Paxos와 Raft 알고리즘과의 관계도 간략히 소개합니다.