Paxos 알고리즘

1 개요

Paxos, Paxos 알고리즘

팩사스 [pǽksas], 팩서스 [pǽksəs], 팩서스 알고리즘

• 신뢰성이 낮은 프로세서의 네트워크에서 합의의 문제를 해결하기 위한 프로토콜 집합
• 참가자의 그룹에서 단일 결과에 대해 합의를 얻는 과정

2 트레이드오프

Paxos 프로토콜 집합은 다음 사항에 대해 트레이드오프가 있다.

• 프로세서의 수
• 합의된 값을 알아낼 때까지의 메시지 지연 ★
• 각 노드의 액티비티 수준
• 송신된 메시지의 수 ★
• 장애의 종류

3 안정성, 활성 특성

• 비 자명성: 제안된 값만 습득한다.
• 완전성: 최대 1개의 값만 습득가능하다.
• 활성: 값 C가 제안되면 습득노드 L은 어떤 값을 습득한다.

4 같이 보기

• CAP 정리
• 유한오토마톤
• Raft 알고리즘

5 참고

• 영어 위키백과 "Paxos (computer science)"