요약 정리

• 합의 알고리즘: Paxos, Raft, Multi-Paxos, Zab
• 트랜잭션 처리: 2PC, 3PC
• 리더 선출: Bully, Ring
• 데이터 복제/동기화: Gossip, Viewstamped Replication
• 시간/순서 정렬: Lamport Clock, Vector Clock
• 분산 키-값 위치 찾기: Chord, DHT

---

분산 합의 알고리즘 (Consensus Algorithms)

분산 시스템에서 여러 노드가 하나의 값을 합의(Consensus) 하는 것이 목적입니다.

알고리즘	특징	장점	단점
Paxos	Leslie Lamport 제안
최초의 이론적 합의 알고리즘	이론적으로 안전성 보장	구현 복잡
이해 어렵고 디버깅 힘듦
Multi-Paxos	Paxos의 최적화 버전
리더 기반 연속 합의	Paxos보다 실용적	여전히 구현 난이도 높음
Raft	Paxos 대안으로 개발
리더 선출, 로그 복제 명확히 분리	이해 쉽고 구현 용이
교육용으로도 적합	Paxos보다 이론적으로 덜 정형화
Viewstamped Replication	Paxos와 유사
리더 기반으로 복제 수행	안정성, 견고함	상대적으로 알려지지 않음
Zab (Zookeeper Atomic Broadcast)	Zookeeper에서 사용
리더 기반 브로드캐스트 프로토콜	실용성 높음, Zookeeper에 최적화	범용 합의 알고리즘으로는 한계

---

분산 트랜잭션 알고리즘

원자성을 보장하는 트랜잭션 처리를 위한 알고리즘입니다.

알고리즘	특징
2PC (Two-Phase Commit)	Coordinator가 Prepare → Commit 단계로 나눠 합의
네트워크 장애 시 block 가능
3PC (Three-Phase Commit)	2PC에 타임아웃과 중간 상태 추가
non-blocking, 하지만 더 복잡

---

리더 선출 알고리즘

리더 노드를 선택하여 시스템을 주도하게 하는 알고리즘입니다.

알고리즘	특징
Bully Algorithm	높은 ID를 가진 노드가 리더가 됨
간단하지만 장애 대응 약함
Ring Algorithm	논리적 링 구조 기반으로 리더 선출
네트워크 안정성이 중요

---

기타 분산 알고리즘

알고리즘	설명
Gossip Protocol	노드 간 랜덤하게 상태 전파 → Eventually Consistent
대규모 분산 시스템에 적합
Chord / DHT	P2P 시스템에서 데이터 위치 찾기
분산 해시 테이블 구조
Vector Clock / Lamport Clock	이벤트 순서 추적
Causal Ordering, 시간 동기화 보완

---

Paxos vs Raft 비교

항목	Paxos	Raft
설계 목적	이론적 완전성	이해하기 쉬운 실용적 합의
복잡도	높음	상대적으로 낮음
리더 선출	암묵적 (Multi-Paxos는 명시적)	명시적
구현	어렵고 다양	비교적 표준화
사용 예	Google Chubby 등	etcd, Consul, RethinkDB 등