팍소스 (컴퓨터 과학)

Paxos는 신뢰할 수 없거나 오류가 발생할 수 있는 프로세서의 네트워크에서 합의를 해결하기 위한 프로토콜 제품군이다. 컨센서스는 참가자들 사이에서 한 가지 결과에 합의하는 과정이다. 참가자나 참가자의 의사소통이 실패할 경우 이 문제는 어려워진다.^[1]

합의 프로토콜은 레슬리 램포트가^[2] 제안하고 프레드 슈나이더가 조사한 분산 컴퓨팅에 대한 주 시스템 복제 접근법의 기초가 된다.^[3] 상태 머신 복제는 알고리즘을 내결함성 분산 구현으로 변환하는 기법이다. 애드호크 기법은 중요한 실패 사례를 미해결로 남길 수 있다. 램포트 외 연구진이 제안한 원칙적인 접근법. 모든 사례가 안전하게 처리되도록 보장한다.

팍소스 의정서는 1989년에 처음 제출되었고 그리스 팍소스 섬에서 사용된 허구적인 입법 컨센서스 시스템의 이름을 따서 명명되었는데, 람포트는 "의회 의원들이 지속적으로 의회를 드나들고 있음에도 불구하고" 의회가 기능해야 한다고 썼다.^[4] 이후 1998년 저널 기사로 출간됐다.^[5]

Paxos 프로토콜 제품군에는 프로세서 수, 합의된 가치를 배우기 전의 메시지 지연 수, 개별 참가자의 활동 수준, 보낸 메시지 수, 실패 유형 사이의 트레이드오프 스펙트럼이 포함된다. 결정론적 오류 방지 합의 프로토콜은 비동기 네트워크에서의 진전을 보장할 수 없지만(피셔^[6], 린치, 패터슨에 의해 논문에서 입증된 결과), 팍소스는 안전성(일관성)을 보장하며, 진보를 방해할 수 있는 조건은 도발하기 어렵다.

Paxos는 일반적으로 내구성이 요구되는 경우(예: 파일이나 데이터베이스를 복제하는 경우), 내구성의 양이 클 수 있는 경우에 사용된다. 프로토콜은 일부 한정된 수의 복제본이 응답하지 않는 기간 동안에도 진전을 시도한다. 영구적으로 실패한 복제본을 삭제하거나 새로운 복제본을 추가하는 메커니즘도 있다.

역사

그 주제는 의전보다 앞서 있다. 1988년, 린치, 드워크 및 스톡마이어는 광범위한 "부분적으로 동기식" 시스템 제품군에서 합의의 해결 가능성을 입증했다. 팍소스는 1988년 오키와 리스크노프가 분산거래라는 맥락에서 처음 발표한 '뷰스탬프 복제'에서 합의에 사용한 프로토콜과 유사성이 강하다.^[8] 이러한 선행 작업에도 불구하고, 팍소스는 특히 우아한 형식주의를 제시했고, 오류 방지 분산 합의 프로토콜에 대한 가장 초기 안전 증명들 중 하나를 포함시켰다.

재구성 가능한 상태 기계는 동적 그룹 멤버십을 지원하는 신뢰할 수 있는 그룹 멀티캐스트 프로토콜의 이전 작업과 강한 연관성을 가지고 있다. 예를 들어, 비르만의 작업은 사실상 동기식 gbcast^[9] 프로토콜에 관한 1985년과 1987년이다. 그러나 gbcast는 내구성을 지원하고 파티셔닝 장애를 해결하는 데 있어 이례적이다. 가장 신뢰할 수 있는 멀티캐스트 프로토콜은 상태 컴퓨터 복제 모델의 구현에 필요한 이러한 속성이 결여되어 있다. 이 점은 람포트, 말키, 저우의 논문에서 상세히 기술되어 있다.^[10]

팍소스 프로토콜은 충돌 실패와 일률적인 합의로 공식화된 문제에 대한 해결책의 이론적 등급의 구성원이다. 이 문제에 대한 하한은 키다르와 슈레이어에 의해 증명되었다.^[11] 클라우드 스케일 상태 머신 복제를 위한 C++ 소프트웨어 라이브러리인 ^[12]데레초는 자체 관리 가상 동기식 멤버십과 통합한 팩소스 프로토콜을 제공한다. 이 프로토콜은 Keidar와 Shraer 최적성 경계를 일치시키고, 현대의 원격 DMA(Remote DMA) 데이터 센터 하드웨어에 효율적으로 매핑한다(그러나 RDMA를 사용할 수 없는 경우 TCP 사용).

가정

팍소스의 표시를 단순화하기 위해 다음과 같은 가정과 정의를 명시한다. 적용가능성을 넓히는 기술은 문헌에 알려져 있으며, 이 글에서는 다루지 않는다.

프로세서

• 프로세서는 임의의 속도로 작동한다.
• 프로세서에 고장이 발생할 수 있다.
• 안정적인 스토리지를 갖춘 프로세서는 고장 후(충돌 복구 실패 모델에 따라) 프로토콜에 다시 가입할 수 있다.
• 프로세서는 결탁하거나 거짓말을 하거나 다른 방법으로 프로토콜을 전복시키려 하지 않는다. (즉, 비잔틴의 실패는 일어나지 않는다. 프로세스의 임의적/악의적 동작에서 발생하는 실패를 용인하는 솔루션은 비잔틴 팍소스를 참조하십시오.)

네트워크

• 프로세서는 다른 프로세서로 메시지를 보낼 수 있다.
• 메시지는 비동기적으로 전송되며 배달하는 데 임의적으로 시간이 걸릴 수 있다.
• 메시지는 분실, 재주문 또는 중복될 수 있다.
• 메시지는 부패 없이 전달된다. (즉, 비잔틴의 실패는 일어나지 않는다. 비잔틴 팩소스에서 메시징 채널의 임의/악의 동작에서 발생하는 손상된 메시지를 허용하는 솔루션을 참조하십시오.)

프로세서 수

$일반적$으로 합의 알고리즘은 어떤 F ${\displaystyle F}$ 프로세서의$$ 동시 실패에도 $불구하고{\displaystyle }$ n${\displaystyle }$= ${\displaystyle 2}$ ${\displaystyle \mathrm{F}}$+ 1 ${\displaystyle n=2F+1}$ 프로세서를$$ 사용하여 진전을 이룰 수 있다.^[13] 즉, 결함이 없는 프로세스의 수는 결함 프로세스 수보다 엄격히 커야 한다. 그러나 재구성을 사용하면 F 이하의 장애가 동시에 발생하지 않는 한 총 장애 수에서 살아남는 프로토콜을 사용할 수 있다. Paxos 프로토콜의 경우, 이러한 재구성은 별도의 구성으로 처리할 수 있다.^[14]

역할

Paxos는 프로토콜에서 프로세서의 역할에 따라 프로세서의 동작을 기술한다: 클라이언트, 인수자, 제안자, 학습자, 리더. 일반적인 구현에서는 단일 프로세서가 동시에 하나 이상의 역할을 수행할 수 있다. 이것은 프로토콜의 정확성에 영향을 미치지 않는다. 프로토콜의 지연 시간 및/또는 메시지 수를 개선하기 위해 역할을 통합하는 것이 보통이다.

고객

클라이언트가 분산 시스템에 요청을 발행하고 응답을 기다리는 경우. 예를 들어 분산 파일 서버의 파일에 대한 쓰기 요청.

수락자(Voters)

수용자는 프로토콜의 내결함성 "메모리" 역할을 한다. 수용자는 Quorum이라고 불리는 그룹으로 수집된다. 수락인에게 보낸 모든 메시지는 수락자의 쿼럼으로 전송되어야 한다. 쿼럼의 각 수락자로부터 사본을 수신하지 않는 한 수락자로부터 수신된 모든 메시지는 무시된다.

제안자

제안자는 고객의 요청을 옹호하며, 수용자가 동의하도록 설득하고, 충돌이 발생할 때 프로토콜을 진전시키기 위한 조정자 역할을 한다.

학습자

학습자는 프로토콜의 복제 팩터 역할을 한다. 고객 요청이 승인자에 의해 합의된 후 학습자는 조치를 취할 수 있다(즉, 요청을 실행하고 고객에게 응답을 보내는 것). 프로세싱의 가용성을 향상시키기 위해 학습자를 추가할 수 있다.

리더

팍소스는 진전을 이루기 위해 뛰어난 프로포저(리더라고 불리는)를 필요로 한다. 많은 과정들이 그들이 리더라고 믿을 수 있지만, 프로토콜은 결국 그들 중 한 명이 선택되어야만 진보를 보장한다. 두 프로세스가 자신들이 리더라고 믿는 경우, 상충되는 업데이트를 지속적으로 제안하여 프로토콜을 지연시킬 수 있다. 그러나 그러한 경우 안전성은 여전히 보존되어 있다.

쿼럼

쿼럼은 최소한 일부 남아 있는 프로세서가 결과에 대한 지식을 유지하도록 함으로써 Paxos의 안전(또는 일관성) 특성을 표현한다.

쿼럼은 두 쿼럼이 적어도 하나의 멤버를 공유하도록 수용자 집합의 하위 집합으로 정의된다. 일반적으로 쿼럼은 참여 수용자의 과반수다. For example, given the set of Acceptors {A,B,C,D}, a majority Quorum would be any three Acceptors: {A,B,C}, {A,C,D}, {A,B,D}, {B,C,D}. More generally, arbitrary positive weights can be assigned to Acceptors; in that case, a Quorum can be defined as any subset of Acceptors with the summary weight greater than half of the total weight of all Accept오즈

제안번호 및 합의가치

합의된 값 v를 정의하려는 각 시도는 수용자가 수용하거나 수용하지 않을 수 있는 제안으로 수행된다. 각 제안에는 주어진 제안자에게 고유 번호가 부여된다. 예를 들어, 각 제안은 형식(n, v)일 수 있다. 여기서 n은 제안서의 고유 식별자이고 v는 실제 제안된 값이다. 번호 제안서에 해당하는 값은 팍소스 프로토콜의 실행의 일부로 계산할 수 있지만, 그럴 필요는 없다.

안전 및 활성 특성

안전성을 보장하기 위해("일명 일관성"이라고도 함) 팍소스는 세 가지 속성을 정의하고 고장 패턴에 관계없이 처음 두 개의 속성을 항상 유지하도록 한다.

유효성(또는 비경쟁성)

제안된 가치만이 선택되고 학습될 수 있다.^[15]

합의(또는 일관성 또는 안전)

두 개의 고유한 학습자가 서로 다른 가치를 배울 수 없음(또는 둘 이상의 결정된 가치가 있을 수 없음)^[15][16]

종료(또는 활성)

값 C가 제안된 경우, 결국 학습자 L은 어떤 가치를 배우게 될 것이다(충분한 프로세서가 결함이 없는 상태로 유지되는 경우).^[16]

Paxos는 종료를 보장받지 못하므로 lavity 속성이 없다는 점에 유의하십시오. 이것은 Fischer Lynch Paterson 불가능 결과(FLP)^[6]에 의해 지원되며, Fischer Lynch Paterson은 일관성 프로토콜은 안전성과 내성, 내결함성 중 두 가지만 가질 수 있다고 말한다. 팍소스의 요점은 내결함성을 보장하고 안전성을 보장한다는 것인 만큼, 릴리티도 장담할 수 없다.

일반적인 배포

Paxos의 대부분의 배치에서, 각각의 참여 과정은 제안자, 수용자, 학습자의 세 가지 역할로 작용한다.^[17] 이렇게 하면 정확성이 저하되지 않고 메시지의 복잡성을 크게 줄일 수 있다.

팍소스에서 고객은 리더에게 명령을 보낸다. 정상 작동 중에 리더는 클라이언트의 명령을 수신하여 새 명령 번호 $i{\displaystyle }$ ${\displaystyle$ i$\}$를 할당하고 일련의 승인자 프로세스에 메시지를 전송하여 컨센서스 $알고리즘$의 i ${\displaystyle i}$ 인스턴스를$$^th 시작한다.^[16]

역할을 병합함으로써 프로토콜은 데이터베이스 커뮤니티의 일반적인 효율적인 클라이언트-마스터-리플리카 스타일 배포로 "clapping"한다.^[18] Paxos 프로토콜(통합된 역할을 가진 구현 포함)의 이점은 안전 속성의 보증이다.

일반적인 구현의 메시지 흐름은 Multi-Paxos 절에서 다룬다.

베이직 팩소스

이 의전은 팍소스 가문의 가장 기본적인 것이다. 기본 팍소스 프로토콜의 각 "인스턴스"(또는 "실행")는 단일 출력값을 결정한다. 그 의전은 몇 차례에 걸쳐 진행된다. 성공적인 라운드는 2상: 1단계(부분 a와 b로 나누어지는 것)와 2단계(부분 a와 부분으로 나누는 것)가 있다. 단계 설명은 아래를 참조하십시오. 우리는 비동기 모델을 가정하므로, 예를 들어 프로세서는 한 단계에 있고 다른 프로세서는 다른 단계에 있을 수 있다는 점을 기억하십시오.

1단계

1a 단계: 준비

제안자는 메시지를 작성하는데, 우리는 이것을 숫자 n으로 식별된 "준비"라고 부른다. n은 제안되고 합의될 수 있는 가치가 아니라 제안자에 의해 (수용자에게 보내질) 이 초기 메시지를 고유하게 식별하는 숫자일 뿐이라는 점에 유의한다. n 숫자는 이 제안자가 이전 준비 메시지에서 사용한 숫자보다 커야 한다. 그런 다음, n이 포함된 준비 메시지를 적어도 수용자 쿼럼에 전송한다. 준비 메시지에는 숫자 n(예: 종종 v로 표시되는 제안 값을 포함하지 않아도 됨)만 포함되어 있다는 점에 유의하십시오. 제안자가 정족수^[how?] 안에 누가 있는지 결정한다. 제안자는 최소한 수용자의 쿼럼과 의사소통할 수 없는 경우 Paxos를 개시해서는 안 된다.

1단계 b: 약속

수락자는 제안자의 준비 메시지를 기다린다. 수락자가 준비 메시지를 수신하는 경우, 수락자는 방금 수신한 준비 메시지의 식별자 번호 n을 확인해야 한다. 두 가지 경우가 있다.

n이 제안자 중 누구로부터든 수용자가 받은 이전의 모든 제안 번호보다 높은 경우, 수용자는 제안자에게 "약속"이라고 부르는 메시지를 반환해야 하며, 이는 n보다 적은 숫자를 가진 모든 미래 제안을 무시하는 것이다. 과거 어느 시점에 수용자가 제안을 수락했다면 제안자에 대한 응답에 이전 제안 번호(예: m)와 그에 상응하는 수용가(예: w)를 포함해야 한다.

그렇지 않으면(즉, n은 수용자가 제안자로부터 받은 이전의 제안 번호보다 작거나 같음) 수용자는 접수된 제안을 무시할 수 있다. 팍소스가 작동하기 위해서는 이 경우에 대답할 필요가 없다. 그러나 최적화를 위해 거부(Nack) 응답을 보내면 제안자에게 제안 n과 합의점을 만들려는 시도를 중단할 수 있음을 알 수 있다.

2단계

단계 2a: 수락

제안자가 수용자 쿼럼으로부터 약속을 받는 경우, 제안서에 가치 v를 설정할 필요가 있다. 이전에 어떤 제안을 수락한 사람이 있다면, 제안자에게 자신의 가치를 보냈을 것이다. 제안자는 이제 제안서의 가치인 v를 수용자가 보고한 최고 제안 번호와 관련된 가치로 설정해야 한다. 이를 z라고 부르자. 만약 어떤 수용자도 지금까지 제안을 수용하지 않았다면, 제안자는 원래 제안하고자 했던 가치를 선택할 수 있다(예: x).^[19]

제안자는 자신의 제안서에 대해 선택된 값인 v와 제안 번호 n(이전에 수용자에게 보낸 준비 메시지에 포함된 숫자와 동일)을 가진 수용자 쿼럼에 수락 메시지(n, v)를 보낸다. 따라서 Accept 메시지는 (n, v=z)이거나, 이전에 수락자가 값을 수락하지 않은 경우(n, v=x)입니다.

이 수락 메시지는 "이 제안을 수락하십시오!"에서와 같이 "요청"으로 해석되어야 한다.

2b 단계: 수락됨

수용자가 제안자로부터 수락 메시지(n, v)를 수신하는 경우, 승인자는 (팩소스 프로토콜의 1b단계에서) n보다 큰 식별자를 가진 제안만 고려하도록 아직 약속하지 않은 경우에만 수락해야 한다.

수용자가 n보다 큰 식별자를 가진 제안만을 고려하기로 (1b 단계에서) 아직 약속하지 않은 경우, 승인자는 ( 방금 수신한 수락 메시지의) v 값을 (프로토콜의) 허용 값으로 등록하고 제안자와 모든 학습자에게 수락된 메시지를 보내야 한다(일반적으로 제안자 자신이 될 수 있다).

그렇지 않으면 메시지 또는 요청을 무시할 수 있다.

수용자는 여러 제안을 수용할 수 있다는 점에 유의하십시오. 이는 새로운 가치가 결정되는 것을 모르는 다른 제안자가 더 높은 식별 번호 n을 가진 새로운 라운드를 시작할 때 발생할 수 있다. 그 경우, 수용자는 이전에 다른 것을 수용했음에도 불구하고 새로운 제안가치를 약속하고 나중에 받아들일 수 있다. 이러한 제안은 심지어 특정한 실패가^{[example needed]} 존재하는 경우에도 다른 가치를 가질 수 있다. 그러나 팍소스 프로토콜은 수용자들이 궁극적으로 단일 가치에 대해 합의할 것을 보장할 것이다.

라운드 실패 시

여러 제안자가 충돌하는 준비 메시지를 보내거나 제안자가 응답 정족수(약속 또는 수락)를 받지 못할 때 회진은 실패한다. 이 경우 더 높은 제안 번호로 다시 한 번 라운드를 시작해야 한다.

팍소는 리더를 선택하는 데 사용될 수 있다.

팍소스의 제안자가 "나는 리더다" (또는 "프로포저 X가 리더다")^[20]를 제안할 수 있다는 점에 유의하십시오. 팍소스의 합의와 유효성 보증으로 인해 쿼럼에 의해 수락될 경우 제안자가 다른 모든 노드의 리더로 알려져 있다. 이는 리더라고 믿는 단일 노드가 있고 항상 리더라고 알려진 단일 노드가 있기 때문에 리더 선거의^[21] 필요를 충족시킨다.

기본 팩소에서의 메시지 흐름 그래픽 표현

다음 도표는 기본 팍소스 프로토콜 적용의 몇 가지 사례/상황을 나타낸다. 일부 사례들은 기본 팍소스 프로토콜이 분산 시스템의 특정 (중복적인) 구성요소의 실패에 어떻게 대처하는지를 보여준다.

Promise 메시지에서 반환되는 값은 제안이 처음 이루어질 때 "null"이라는 점에 유의하십시오(이 라운드에서는 이전에 수락자가 값을 수락하지 않았으므로).

고장 없는 기본 팩소

아래 도표에는 클라이언트 1명, 제안자 1명, 수용자 3명(정족수 크기는 3) 및 학습자 2명(수직선 2개로 표시됨)이 있다. 이 다이어그램은 성공적인 1라운드(즉, 네트워크의 어떤 프로세스도 실패하지 않음)의 경우를 나타낸다.

클라이언트 Proposer Acceptor 예비 X?>요청 X?->, ->, ->, Prepare(1)<-----X--X--XPromise(1,{Va,Vb,Vc})X?->, ->, ->, 받아들이십시요!(1,V).          <-----X--X--X------> -> 합격(1,V) <------------------------------------------X-반응                                            

여기서 V는 (Va, Vb, Vc)의 마지막이다.

기본 팍소스의 오류 사례

가장 간단한 오류 사례는 수용자의 실패(수용자의 쿼럼이 존속된 경우)와 중복 학습자의 실패다. 이러한 경우 프로토콜은 "복구"를 요구하지 않는다(즉, 여전히 성공). 아래(다음 두 다이어그램/사례에서)와 같이 추가 라운드나 메시지가 필요하지 않다.

Acceptor 실패 시 기본 Paxos

다음 다이어그램에서 쿼럼의 승인자 중 한 명이 실패하므로 쿼럼 크기는 2가 된다. 이 경우 베이직 팍소스 프로토콜은 여전히 성공한다.

클라이언트 Proposer Acceptor 예비 X?>요청 X?->, ->, ->, Prepare(1)!!!FAIL!<-----X--XPromise(1,{Va, 퓨, null})X?->, -&gt을 말한다.                 수락!(1,V) <---------X-X-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------반응                                            

중복 학습자가 실패하는 경우 기본 팩소

다음의 경우, (중복) 학습자 중 한 명이 실패하지만, 기본 팍소스 프로토콜은 여전히 성공한다.

클라이언트 Proposer Acceptor 예비 X?>요청 X?->, ->, ->, Prepare(1)<-----X--X--XPromise(1,{Va,Vb,Vc})X?->, ->, ->, 받아들이십시요!(1,V).         <-----X--X, X-----> -> 합격(1,V)!!! 불합격!!!!------------------------------------------------------------------------------------------------------------------------------------------                                         

제안자의 실패 시 기본 팩소스

이 경우 제안자는 가치를 제안하고 난 후, 그러나 합의가 이루어지기 전에 실패한다. 구체적으로 Accept 메시지 중간에 실패하기 때문에, 쿼럼의 Acceptor 1명만이 그 값을 받는다. 한편, 새로운 지도자(제안자)가 선출된다(그러나 이것은 자세히 보여지지는 않는다). 이 경우 라운드가 2회(라운드는 위에서 아래로 수직으로 진행됨)된다는 점에 유의하십시오.

고객 제안자 수용자 학습자 X----> 요청 X---------------------------------------------------------X-X-X 약속 (1,{Va, Vb, Vc})                                                                                        !!지도자 방송에서!X------------<>입니다를 받아들이십시요!(1,V)!!!NEWLEADER!X?->, ->, ->, Prepare(2)<-----X--X--XPromise(2{V, 여백 null})실패했습니다.             X?->, ->. -> 수용하라!(2,V) <-------------X-X-X-----> 수용 (2,V) <--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------                                            

여러 제안자가 충돌할 때 기본 팩소스

가장 복잡한 경우는 다수의 제안자가 자신이 리더라고 믿는 경우다. 예를 들어, 현재 리더는 실패하여 나중에 회복될 수 있지만, 다른 제안자들은 이미 새로운 리더를 다시 선택했다. 회복된 지도자는 아직 이것을 배우지 못했고 현재의 지도자와 충돌하여 한 라운드를 시작하려고 시도한다. 아래 다이어그램에는 실패한 라운드가 4개 표시되지만, 더 많은 라운드가 있을 수 있다( 다이어그램 하단에 제시됨).

고객 제안자 수용자 학습자 X---> 요청 X--------------------------------------------------------------X-X 약속(1,{null,null,null})!! 리더 실패!                                             !! 새 리더 (마지막 번호가 1) X---------------------------------------------------------------------------------------------X-X 약속 (2,{null, null})!! 올드 리더 회복!! 늙은 리더는 2, 거부 X----------------------------------------------------------------------------------X-X n!! 올드 리더는 3X-----------------------------------------------------------------------------X-X-X 약속 (3,{null, null})을 시도한다!! NEWLEADER, X을 부인했다----->, ->, ->, 받아들이십시요!(2,Va)<-----X--X--XNack(3)!NEWLEADER 4X노력할까?->, ->, ->, Prepare(4)<-----X--X--X약속(4,{null,null,nu을 제안한다.주어})                                             !! Old Leader proposed, 거부된 X---------------------------------------------------------------------------------------------> -> 수락!(3,Vb) <--------X-X-X-X Nack(4) ... 등...  

멀티팩소스

전형적인 팍소스의 배치는 분산된 상태 기계에 대한 명령의 역할을 하는 합의된 값의 연속적인 스트림을 필요로 한다. 각 명령이 기본 팍소스 프로토콜의 단일 인스턴스의 결과라면 상당한 오버헤드가 발생할 것이다.

리더가 상대적으로 안정적이면 1단계는 불필요해진다. 따라서, 동일한 리더를 가진 프로토콜의 미래 인스턴스들을 위해 1단계를 건너뛸 수 있다.

이를 위해 라운드 번호가 각 라운드에서 동일한 리더에 의해 증가되는 각 값과 함께 포함된다. 멀티팩소스는 무장애 메시지 지연(학습에 대한 제안)을 4회 지연에서 2회로 줄인다.

Multi-Paxos에서의 메시지 흐름 그래픽 표현

고장 없는 멀티팩소

다음 다이어그램에서는 초기 리더(제안자)가 있는 기본 팍소스 프로토콜의 인스턴스(또는 "실행")가 하나만 표시된다. Multi-Paxos는 기본 Paxos 프로토콜의 여러 인스턴스로 구성된다.

클라이언트 Proposer Acceptor 예비-먼저 요청..-X?>요청 X?->, ->, ->, Prepare(N)<-----X--X--XPromise(N,I,{Va,Vb,Vc})X?->, ->, -&gt을 말한다.            !(N,I,V)를 수락하다.               <----------X-X-X-X-----> -> 합격(N, I,V) <---------------------------------------------------------------------------------X 반응                                            

여기서 V = 마지막(Va, Vb, Vc)

1단계를 건너뛸 수 있는 경우 다중 팩소스

이 경우 기본 팍소스 프로토콜의 후속 인스턴스(I+1)는 동일한 리더를 사용하므로, 준비 및 약속 하위 페이즈로 구성된 단계 1(이 기본 팍소스 프로토콜의 후속 인스턴스 중)은 생략한다. 리더는 안정적이어야 한다. 즉, 리더가 충돌하거나 변화해서는 안 된다.

클라이언트 Proposer Acceptor 예비-Following 요청..-X?>요청 X?->, ->, ->, 받아들이십시요!(N,I+1,W)<-----X--X--X---->->, Accepted(N,I+1,W)<>------------------------------.---X--X응답                                                                                 

역할이 축소될 때 다중 팩소스

Multi-Paxos의 공통적인 배치는 "서버"에 대한 제안자, 수용자 및 학습자의 역할을 붕괴시키는 것이다. 그래서 결국 '고객'과 '서버'밖에 없다.

다음 도표는 제안자, 수용자 및 학습자의 역할이 "서버"라고 불리는 단일 역할로 축소되는 기본 팍소스 프로토콜의 첫 번째 "인스턴스"를 나타낸다.

Client      Servers                      --- First Request ---    X-------->         Request              X-> ->   Prepare(N)               <-X--X  Promise(N, I, {Va, Vb})              X-> ->   Accept!(N, I, Vn)              X<>X<>X  Accepted(N, I)     <--------X        Response                      

역할이 축소되고 리더가 꾸준할 때 멀티팩소스

기본 팍소스 프로토콜의 후속 사례에서는, 기본 팍소스 프로토콜의 이전 사례와 동일한 리더로, 1단계를 생략할 수 있다.

클라이언트 서버 X--------> 요청 X-> -> 수락!(N,I+1,W) X<X 수락(N,I+1) <----X 응답                      

최적화

교환된 메시지의 수를 줄이고 프로토콜의 성능을 향상시키기 위해 여러 가지 최적화를 수행할 수 있다. 이러한 최적화 중 몇 가지를 아래에 보고한다.

"우리는 가치가 선택되었다는 것을 알게 되면 다른 학습자에게 알려주는 하나의 뛰어난 학습자를 보유함으로써 추가 메시지 지연에 따른 비용으로 메시지를 저장할 수 있다. 그런 다음, 수락자는 저명한 학습자에게만 승인된 메시지를 발송한다. 대부분의 애플리케이션에서 리더와 뛰어난 학습자의 역할은 동일한 프로세서에 의해 수행된다.^[22]

"지도자는 그것의 준비와 수용! 메시지를 수용자 정족수에게만 보낼 수 있다. 그 정족수 안에 있는 모든 수용자가 일을 하고 있고 리더와 학습자와 의사소통이 가능한 한, 수용자가 정족수 안에 있지 않은 것은 아무것도 할 필요가 없다.^[22]

"수용자들은 어떤 가치가 선택되든 상관하지 않는다. 그들은 실패에도 불구하고 오직 하나의 값만 선택할 수 있도록 하기 위해 준비와 수용! 메시지에 응답한다. 그러나, 수용자가 어떤 가치를 선택했는지 알게 되면, 그 가치를 안정적인 저장소에 저장하고, 거기에 저장한 다른 정보를 지울 수 있다. 만약 수용자가 나중에 그 단계1b 또는 단계2b 액션을 수행하는 대신에 준비 또는 수용! 메시지를 받는다면, 그것은 단순히 리더에게 선택된 값을 알릴 수 있다.^[22]

"리더는 v 값을 보내는 대신 수락 메시지에서 일부 수락자에게 v의 해시를 보낼 수 있다. 학습자는 수용자 쿼럼에서 v 또는 해당 해시에 대해 수락된 메시지를 수신하고 해당 메시지 중 하나 이상이 해시가 아닌 v를 포함하는 경우 v가 선택된다는 것을 배우게 된다. 그러나 리더는 v의 실제 값을 알리지 않고 phase2a 동작에 반드시 사용해야 하는 값 v의 해시를 알려주는 Promise 메시지를 받을 수 있다. 그렇게 되면 리더는 v를 알고 있는 어떤 프로세스와 통신할 때까지 phase2a 동작을 실행할 수 없다."^[22]

제안자는 모든 코디네이터가 아닌 리더에게만 제안서를 보낼 수 있다. 단, 이를 위해서는 리더 선정 알고리즘의 결과를 제안자에게 방송해야 하는데, 비용이 많이 들 수도 있다. 그래서 제안자에게 제안서를 모든 코디네이터에게 보내도록 하는 것이 좋을 수 있다.(그 경우 코디네이터 자신만 리더가 누구인지 알면 된다.)^[15]

"각각의 수용자가 각 학습자에게 수용된 메시지를 보내는 대신, 수용자는 자신의 수용된 메시지를 리더에게 보내고 리더는 가치가 선택되었을 때 학습자에게 알릴 수 있다. 그러나 이것은 추가적인 메시지 지연을 추가한다.^[15]

"마지막으로 1단계는 1라운드에서 불필요하다는 것을 관찰하라. 1라운드의 리더는 제안된 가치가 있는 수락 메시지를 보내면 라운드를 시작할 수 있다."^[15]

값싼 팍소스

싸구려 팩소스는 F+1 메인 프로세서와 F 보조 프로세서로 F 장애를 견딜 수 있도록 기본 팩소스를 확장하여 각각의 고장 후 동적으로 재구성한다.

프로세서 요구사항의 이러한 감소는 lability를 희생하여 발생한다. 단시간에 너무 많은 메인 프로세서가 고장날 경우, 보조 프로세서가 시스템을 재구성할 수 있을 때까지 시스템은 중지되어야 한다. 안정된 기간 동안 보조 프로세서는 프로토콜에 관여하지 않는다.

"프로세서 p와 q만 두 개면 한 프로세서가 다른 프로세서의 고장과 통신 매체의 고장을 구분할 수 없다. 세 번째 프로세서가 필요하다. 그러나 그 세 번째 프로세서는 명령의 순서를 선택하는 데 참여하지 않아도 된다. p 또는 q 중 하나가 스스로 시스템을 계속 작동시키는 동안 p 또는 q가 실패한 경우에만 조치를 취해야 한다. 따라서 세 번째 프로세서는 소형/저속/저속 또는 주로 다른 작업에 전용되는 프로세서가 될 수 있다."^[22]

메시지 흐름: 싸구려 멀티팩소스

한 개의 메인 프로세서의 실패와 후속 재구성을 보여주는 세 개의 기본 수용자(보조 수용자 1명 및 쿼럼 크기 3명)가 포함된 예:

            {Acceptors}Proposer 메인 오 예비-2단계는--X----------->, ->, ->, 받아들이십시요!(N,I,V)!..-FAIL!..-<>-----------X--X------------->, Accepted(N,I,V), 실패,(겨우 2합격)를 감지했습니다.X----------->-> 할 것이며,--->, 받아들이십시요!(N,I,V)(re-transmit, 오 포함한다)<>-----------X--X------X---->Accepted(N,I,V)--재구성:쿼럼=2--X----------->, ->, 받아들이십시요!(N,I+1,W)(보조 참여하지 않)<>-----------X--X------------->, 받아들여진(N,I+1.,W)                                                

패스트팩소스

패스트팩소스는 베이직팩소스를 일반화하여 종단간 메시지 지연을 줄인다. 베이직 팩소스에서, 고객 요청에서 학습으로의 메시지 지연은 3개의 메시지 지연이다. Fast Paxos는 2개의 메시지 지연을 허용하지만, (1) 시스템은 (클래식 2f+1 대신) 최대 f 결함을 허용하도록 3f+1 수용자로 구성되고, (2) 클라이언트가 요청을 여러 목적지에 전송하도록 요구한다.

직관적으로 리더가 제안할 가치가 없는 경우, 고객은 수용자에게 직접 수락 메시지를 보낼 수 있다. 수용자는 기본 팩소(Basic Paxos)와 같이 응답하여 리더에게 수락 메시지를 보내고 모든 학습자는 클라이언트에서 학습자에게 두 가지 메시지 지연을 달성한다.

리더가 충돌을 감지할 경우, 평상시처럼 수락된 새 라운드에 대해 수락 메시지를 보내 충돌을 해결한다. 이 조정된 복구 기법은 클라이언트에서 학습자에게 네 가지 메시지 지연을 요구한다.

최종 최적화는 리더가 미리 복구 기법을 지정했을 때 발생하며, 이를 통해 수용자가 직접 충돌 복구를 수행할 수 있다. 따라서 조정되지 않은 충돌 복구는 세 가지 메시지 지연(모든 학습자가 수용자인 경우 두 가지 메시지 지연)에서 발생할 수 있다.

메시지 흐름: 고속 팩소, 충돌 없음

Client지도자 Acceptor 예비 X?->, ->, ->, ->, Any(N,I,Recovery)X--------------->, ->, ->, ->, 받아들이십시요!(N,I,W)<-----X--X--X--X---->->, Acce.pted(N,I,W)<-------------------------------------------------X 응답(W)                                               

메시지 흐름: Fast Paxos, 상충되는 제안

조정된 복구와 상충되는 제안. 참고: 프로토콜은 삭제된 클라이언트 요청을 처리하는 방법을 지정하지 않는다.

고객 리더 수락자 학습자 !! 동시 충돌 제안 !!! 수용자 X------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------? 수용! (N,I,W) 수용)                                                                                    !! 수용자는 값 <------X-X-> -> ----> -> 수용자(N,I,V) <------- <-X-X-X-X-> -> 수용자(N,I,W)!! 충돌을 감지하고 X-------> -> -> -> -> -> 수용!(N+1,I,W) <---------X-X-X-X-X-X--> -> 수락(N+1,I,W) <---------------------------------------------------------X-X 응답(W)                                          

조정되지 않은 복구로 상충되는 제안.

클라이언트 리더 수용자 학습자 X-------> -> -> -> -> 임의(N, I, 복구)!! 동시 충돌 제안 !!! 수용자 X------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------? 수용! (N,I,W) 수용)                                                                                    !! 수용자는 값 <------X-X-> -> ----> -> 수용자(N,I,V) <------- <-X-X-X-X-> -> 수용자(N,I,W)!! 충돌 감지 및 복구 <-----X-X-X-X-X-X--> -> 합격(N+1,I,W) <-----------------------------------------------------X-X 반응(W)                                          

메시지 흐름: 조정되지 않은 복구, 축소된 역할의 빠른 Paxos

(수락자/학습자 역할 포함)

클라이언트 서버 X->> -> -> Any(N, I, 복구)!! 동시에 충돌하는 제안 !! 서버 X---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------? 수용 값 X<X-> -> Accepted (N, I, V) <- <- X<X Accepted (N, I, W)!! 충돌 감지 및 복구 X<X<X> 수락(N+1,I,W) <------X-X-X-X-X-X 응답(W)                          

일반화 팩소스

일반화된 합의는 복제된 국가 기계의 운영과 그것을 구현하는 합의 프로토콜 사이의 관계를 탐구한다.^[16] 주요 발견은 상충되는 제안이 어떤 순서로든 적용될 수 있을 때, 즉 제안된 운영이 주 기계에 대한 역방향 운영일 때 팍소스의 최적화를 포함한다. 이 경우 갈등해결에 필요한 지연을 피하고 거부된 작전을 재제안하는 등 상반된 작전을 모두 수용할 수 있다.

이 개념은 더욱 일반화되어 점점 증가하는 정류 연산 순서에 따라, 일부는 안정적이라고 알려져 있다(따라서 실행될 수도 있다). 프로토콜은 이러한 시퀀스를 추적하여 한 시퀀스의 모든 제안된 운영이 안정화되도록 보장한 후 비 커밋 작업이 안정화되도록 한다.

예

일반화 팍소스를 설명하기 위해, 아래의 예는 동시에 실행되는 두 클라이언트와 두 개의 별개의 레지스터 A와 B에 대해 읽기/쓰기 작업을 구현하는 복제된 상태 기계 사이의 메시지 흐름을 보여준다.

정류율표

	읽기(A)	쓰기(A)	읽기(B)	쓰기(B)
읽기(A)
쓰기(A)
읽기(B)
쓰기(B)

이 표는 비규범적인 작업을 나타낸다는 점에 유의하십시오.

가능한 작동 순서:

 <1:읽기(A), 2:읽기(B), 3:쓰기(B), 4:읽기(B), 5:읽기(A), 6:쓰기(A)> 

이후 5:Read(A) 양쪽 모두와 통근하다. 3:Write(B) 그리고 4:Read(B), 이전 순서와 동등한 한 가지 가능한 순열은 다음과 같다.

 <1:읽기(A), 2:읽기(B), 5:읽기(A), 3:쓰기(B), 4:읽기(B), 6:쓰기(A)> 

실제로 통근은 동시에 운영이 제안될 때만 발생한다.

메시지 흐름: 일반 팍소스(예)

응답이 표시되지 않음 참고: 메시지 약어는 프로토콜의 세부사항으로 인해 이전 메시지 흐름과 다르다. 자세한 내용은 을 참조하십시오.

고객 리더 수락자 학습자 !! 새로운 리더가 라운드 X----> -> -> -> 준비 (N) <-----X-X-X-X-X 약속 (N,null) X---> -> -> 단계2시작 (N,null)!! Concurrent commuting proposals     X------- ? -----? -? -?                Propose(ReadA)  X-----------? -----? -? -?                Propose(ReadB)               X------X--------------> ->   Accepted(N,<ReadA,ReadB>)                <--------X--X--------> ->   Accepted(N,<ReadB,ReadA>)                                                                                      !! 충돌 없음, 둘 다 수용된 안정 = <ReadA, ReadB>!! Concurrent 상반되는 제안 X-----------?---?-?-?Propose(<>WriteB,ReadA>.)X??---?-?-?Propose(ReadB)X----X------------>->, 받아들여진(N,&lt을 말한다.WriteB,ReadA>..<>ReadB>^<------X--X?>->, 받아들여진(N,<, ReadB>..<>Writ.eB,ReadA>) !! 갈등은, 지도자 교환 주문:V=<>ReadA, WriteB, ReadB>, X--->, ->, ->, Phase2Start(N+1,V)<---X- X-X?>->.(N+1,으로 수용 선택하고 있다.V=                                            안정 = <ReadA, ReadB>. <ReadA, WriteB, ReadB>!! 더욱 상반되는 제안 X-----------?---?-?-?Propose(WriteA)X??---?-?-?Propose(ReadA)X----X------------>->, Accepted(N+1,<, WriteA>..<>ReadA>.)<----X-X?>->, 받아들여진(N+1,<, 알eadA>..<>WriteA>^                                                                                      !! 지시선 선택:                                            W = <WriteA, ReadA> X------> -> -> 위상2Start(N+2,W) <-----X-X-X-X--------> -> Accepted(N+2,W) Stabil = <ReadA, ReadB>. <R>eADA, WriteB, ReadB > . <WritA, ReadA>                                           

퍼포먼스

위의 메시지 흐름은 일반화 팩소스가 네트워크의 자발적 순서가 실패할 때 충돌을 피하기 위해 운용 의미론을 활용할 수 있다는 것을 보여준다. 이것은 프로토콜이 Fast Paxos보다 더 빨리 실행되도록 한다. 그러나 충돌이 일어나면 일반화 팩소스는 회복하기 위해 두 번의 추가 왕복 여행이 필요하다. 이러한 상황은 위의 스키마에서 WriteB와 ReadB 연산으로 설명된다.

일반적인 경우, 이러한 왕복은 피할 수 없으며, 라운드 중에 여러 명령을 받아들일 수 있다는 사실에서 비롯된다. 이로 인해 충돌이 잦을 때 프로토콜 비용이 팍소스보다 비싸진다. 일반화 팍소스의 두 가지 가능한 개선이 회복 시간을 향상시킬 수 있기를 바란다.^[24]

• 첫째, 코디네이터가 모든 수용자 쿼럼의 일부인 경우(반올림 N은 중심이라고 함), 그 다음 라운드 N에서의 충돌로부터 라운드 N+1에서 회복하기 위해 코디네이터는 1단계를 건너뛰고 2단계에서 마지막으로 수락한 순서를 제안한다. 이렇게 하면 복구 비용이 단 한 번의 왕복으로 줄어든다.
• 둘째, N과 N+1 라운드가 모두 고유하고 동일한 중심 정족수를 사용하는 경우, 수용자가 N 라운드에서 충돌을 감지할 때, N+1 라운드에서 (i) 코디네이터가 N 라운드에서 수락한 시퀀스와 (ii) N 라운드에서 수락한 최대 비충돌 접두사 둘 다에 접미사를 자동으로 제안한다. 예를 들어, 코디네이터와 수용자가 각각 라운드 N <WriteB, ReadB>와 <ReadB, ReadA>에서 수락하면, 수용자는 라운드 N+1에서 자발적으로 <WriteB, ReadB, ReadA>를 수락하게 된다. 이러한 변화로 인해 복구 비용은 단일 메시지 지연으로, 이는 분명히 최적이다. 라운드에서 고유한 쿼럼을 사용해도 활성도가 손상되지 않는다는 점에 유의하십시오. 이는 이 쿼럼의 모든 프로세스가 다음 라운드 준비 단계의 읽기 쿼럼이라는 사실에서 비롯된다.^[25]

비잔틴 팍소스

또한 거짓, 메시지 조작, 다른 참가자와의 유착, 선택적 불참 등 참가자의 자의적 실패를 지원하기 위해 팍소스를 연장할 수 있다. 이러한 유형의 실패는 램포트에 의해 대중화된 해결책의 이름을 따서 비잔틴 실패라고 불린다.^[26]

카스트로와 리스크노프가 도입한 비잔틴 팍소스는^[27] 지식을 보급하고 다른 프로세서의 동작을 검증하는 역할을 하는 추가 메시지(Verify)를 덧붙인다.

메시지 흐름: 비잔틴 멀티팩소스, 안정된 상태

클라이언트 Proposer Acceptor 예비 X?>요청 X?->, ->, ->, 받아들이십시요!(N,I,V)X&lt하여<>X&lt하여<>XVerify(N,I,V)-BROADCAST<-----X--X--X---->->, Accep.ted(N,V)<>---------- 그럴까?-----------------X-X 응답(V)                                            

마틴과 알비시에 의해 소개된 패스트 비잔틴 팍소스는^[28] 의뢰인이 수용자들에게 직접 명령을 보내기 때문에 이 추가적인 지연을 제거한다.

Fast Viantine Paxos의 Accepted 메시지는 모든 Acceptors와 모든 학습자에게 전송되며 Fast Paxos는 학습자에게만 Accepted 메시지를 보낸다는 점에 유의하십시오.

메시지 흐름: 빠른 비잔틴 멀티팩소스, 안정된 상태

고객 수용자 학습자 X----> -> -> 수용!(N, I, V) X<X------> 수용 - 수용됨(N, I, V) - 브로드캐스트 <----------------X-X 응답(V)                              

고장 시나리오는 두 프로토콜 모두에서 동일하다. 각 학습자는 서로 다른 수용자로부터 동일한 F+1 메시지를 수신할 때까지 기다린다. 이렇게 되지 않으면 수용자 자신도 (방송 라운드에서 서로의 메시지를 교환했기 때문에) 이를 인지하게 되며, 올바른 수용자는 합의된 가치를 재방송하게 된다.

메시지 흐름: 고속 비잔틴 멀티팩소스, 실패

고객 수용자 학습자!!! 한 수용자는 결함이 있는 X-->-> -> ->! 수용!(N, I, V) X<X---------> 수용됨(N, I,{V,W}) - 브로드캐스트!!! 학습자는 2개의 다른 명령을 받는다!!! 수락자 알림 오류를 수정하고 X<X<X----------> -> 수락됨(N,I,V) - 브로드캐스트 <--------------------X-X 응답(V)!            

RDMA 네트워크에 대한 Paxos 적응

원격 DMA(Remote DMA)를 지원하는 초고속 신뢰성 있는 데이터 센터 네트워크의 출현과 함께, 네트워크 인터페이스 카드와 네트워크 라우터가 신뢰성 및 네트워크 계층 정체 제어를 제공하여 호스트 CPU를 다른 작업에 자유롭게 하는 하드웨어 오프로딩을 활용하도록 Paxos를 최적화하는 데 상당한 관심이 있었다. 데레초 C++ 팍소스 라이브러리는 이 옵션을 탐구하는 오픈 소스 팍소스 구현이다.^[12]

데레초는 완전 종료/재시작 시퀀스에 걸친 데이터 내구성과 메모리 내 복제 및 상태-기계 동기화를 위한 수직 팍소(원자 멀티캐스트)를 모두 제공한다. 데레초에서 채용한 팍소스 프로토콜은 비동기 데이터 스트리밍을 최대화하고 리더의 임계 경로에서 다른 지연원을 제거하기 위해 조정될 필요가 있었다. 그래서 데레초는 양방향 RDMA 데이터 전송 속도를 유지할 수 있다. 대조적으로, 기존의 팍소스 프로토콜은 단순히 메시지 송신 작업을 네이티브 RDMA 작업에 매핑함으로써 RDMA 네트워크로 마이그레이션할 수 있지만, 그렇게 함으로써 중요한 경로에 왕복 지연을 남긴다. 고속 RDMA 네트워크에서는 작은 지연이라도 전체 잠재적 대역폭의 활용을 막을 수 있을 만큼 충분히 클 수 있다.

팍소스의 생산용도

이 섹션은 검증을 위해 추가 인용구가 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "팍소스" 컴퓨터 과학 – 뉴스 · 신문 · 책 · 학자 · JSTOR (2018년 10월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

• 구글은 자사의 Coby distributed lock 서비스에 Paxos 알고리즘을 사용해 실패 시 복제본을 일관적으로 유지한다. 구글 애널리틱스 등에서 생산 중인 빅테이블이 통통한 제품을 사용하고 있다.
• 구글 스패너와 메가스토어는 팍소스 알고리즘을 내부적으로 사용한다.
• OpenReplica 복제 서비스는 사용자가 내결함성 객체를 만들 수 있는 개방형 액세스 시스템의 복제본을 유지하기 위해 Paxos를 사용한다. 동시 라운드를 통해 높은 성능을 제공하고 동적 멤버십 변경을 통해 유연성을 제공한다.
• IBM은 IBM SAN Volume Controller 제품에서 Paxos 알고리즘을 사용하여 클러스터에서 제공하는 스토리지 가상화 서비스의 구성 및 제어 구성 요소를 실행하는 데 사용되는 범용 장애 방지 가상 머신을 구현한 것으로 추정된다(Original MIT & IBM 연구서).
• Microsoft는 Bing의 Autopilot 클러스터 관리 서비스와 Windows Server Failover Clustering에서 Paxos를 사용한다.
• WANdisco는 DConE 액티브-액티브 복제 기술 내에 Paxos를 구현했다.^[29]
• XtreemFS는 파일 데이터와 메타데이터의 내결함성 및 일관성 있는 복제를 위해 Paxos 기반 리스 협상 알고리즘을 사용한다.^[30]
• Heroku는 일관된 분산형 데이터 저장소를 위해 Paxos를 구현하는 Dozerd를 사용한다.
• Ceph는 모니터 프로세스의 일부로 Paxos를 사용하여 어떤 OSD가 클러스터 내에 있는지 합의한다.
• Clustrix 분산 SQL 데이터베이스는 분산 트랜잭션 해결을 위해 Paxos를 사용한다.
• Neo4j HA 그래프 데이터베이스는 Paxos를 구현하여 Apache ZooKeeper를 v1.9에서 대체함
• Apache Cassandra NoSQL 데이터베이스는 경량 트랜잭션 기능에만 Paxos를 사용한다.
• Amazon Elastic Container Services는 Paxos를 사용하여 클러스터 상태에 대한 일관된 뷰를 유지

참고 항목

• 찬드라-투에그 컨센서스 알고리즘
• 상태 기계
• 뗏목

참조

외부 링크

• 레슬리 램포트 홈페이지
• 팍소스 심플
• 적당히 복잡하게 만든 팍스
• 팍소스 알고리즘 재방문
• 팍소스 커밋
• Google 백서: 통통한 분산 잠금 서비스
• Google 백서: 구조화된 데이터를 위한 빅테이블 A 분산 스토리지 시스템
• 팍소스 알고리즘 조사(2007)
• OpenReplica Open Replication 서비스
• FTFile: Fault Tolerance 파일 라이브러리
• Isis2 라이브러리(SafeSend president는 Paxos의 무료 오픈 소스 구현)
• 맹자(Mencius) - 지역분산 시스템을 위한 순환 회전 팍소
• WANdisco - Hadoop, Subversion & GIT용 Active-Active 복제 솔루션
• libpaxos, Paxos 알고리즘의 오픈 소스 구현 모음입니다.
• paxos 분산 컨센서스 알고리즘의 C++ 구현인 libpaxos-cpp
• JBP - 자바 비잔틴 팍소스
• 에를팍소스, 에를랑 별 팍소스
• paxos - Python & Java에서 직진 팍소 구현
• 맨해튼 팍소스(mpaxos), C의 팍소스(paxos)는 복수의 팍소 그룹과 그 전체의 효율적인 거래를 지원한다.
• Neo4j를 사용한 클러스터링
• HT-팍소스
• 팍소스스토어, 위챗에서 팍소스 구현
• LWT 인 카산드라
• Google TechTalks: 팩소스 알고리즘