분산 합의 재검토 (Part I): Paxos 의 일반화 및 안전성 증명
Source
Evernote/Inbox/Distributed consensus revised – Part I – the morning paper.md
Summary
이 문서는 Howard 의 박사 논문 ‘Distributed consensus revised’ 의 Part I 을 소개하며, 분산 시스템에서 단일 값에 대한 합의 (Consensus) 문제의 본질을 탐구한다. 논문은 Paxos 알고리즘의 안전성 (Safety) 과 진전 (Progress) 요구사항을 16 개의 보조정리 및 정리를 통해 엄밀하게 증명하고, 기존 Paxos 가 가진 과잉 설계 요소를 식별한다. 이를 통해 쿼럼 교차, 단계 완료, 값 선택 등의 요구사항을 완화하여 Paxos 를 일반화 (Generalize) 함으로써, 성능과 신뢰성 간의 트레이드오프를 개선하고 확장성을 높일 수 있는 새로운 해결 공간의 가능성을 제시한다.
Key Points
- 분산 합의의 핵심 요구사항: 비자명성 (Non-triviality), 안전성 (Safety), 안전한 학습 (Safe learning), 진전 (Progress), 궁극적 학습 (Eventual learning) 의 5 가지 조건을 정의.
- Paxos 의 엄밀한 증명: 기존 Paxos 알고리즘이 10 가지 속성을 기반으로 안전성과 진전을 보장함을 16 개의 수학적 증명으로 확인.
- Paxos 의 일반화: 증명 과정에서 Paxos 의 일부 속성은 필수적이지 않음을 발견하고, 쿼럼 교차 및 단계 완료 등의 조건을 완화하여 알고리즘을 일반화.
- 기존 Paxos 의 한계: 다수결 (Majority) 의존성으로 인한 확장성 부족 (보통 3~5 노드 제한) 및 네트워크 파티션, 느린 호스트 등 다양한 실패 시나리오에서의 합의 실패 가능성 지적.
- 단일 Acceptor 알고리즘 분석: 가장 단순한 합의 알고리즘으로 안전성은 만족하지만 단일 장애점 (SPOF) 이 존재하여 진전 (Progress) 이 보장되지 않음을 설명하며, 이를 해결하기 위해 다중 Acceptor(Paxos) 로의 전환 필요성 제시.