bluebrown

개인적으로 팩소스 알고리즘을 공부하다가 번역하여 정리한 부분을 공개한다. 전체적인 내용은 Lamport의 Paxos Made Simple에서 가져왔으며, 일부분만 번역이 되어 있다. 혹시 내용상, 번역상 잘못된 부분이 있으면 알려주신다면 감사하겠다.

팩소스 알고리즘은 분산 시스템의 결함 허용 방식의 하나이다.
이는 결함이 있는 분산 시스템이 합의된 하나의 제안을 공유할 수 있도록 설계되어 있다.

우리는 제안의 합의를 다음과 같이 정의한다.

조건 0. 제안의 합의는 제안이 과반수의 수락자에게 인정된 경우에 한한다.

팩소스 알고리즘은 다음과 같이 이루어져 있다.
제안번호상정: 제시자는 유일한 제안번호를 선택하여 과반수의 수락자에게 상정한다.
제안번호인정: 수락자는 존재한다면 이전에 수락한 제안을 첨부하여 응답해 준다.
제안상정: 제시자는 과반수의 수락자로부터 응답을 모은 후, 제안을 상정한다. 이 때, 첨부된 제안이 있다면, 상정되는 제안 값은 이들 중 가장 최신의 것을 사용해야 한다.
제안인정: 수락자는 최근에 인정한 제안번호 이상의 제안번호를 가진 제안만을 인정한다.

우리는 제안이 단 한 번 제시되었을 경우에도 합의가 이루어지길 원하기에, 다음 조건을 제시한다.

조건 1. 수락자는 처음 제시되는 제안은 무조건 인정하여야 한다.

하지만, 여러 제안이 복수의 제안자로부터 제시될 수 있기 때문에, 모든 수락자가 각각 제안을 인정하였음에도 불구하고 과반수의 합의에 이르는 제안이 없을 수가 있다. 그러므로 조건 0과 조건 1을 모두 만족시키기 위해서는, 수락자는 여러 번 제안을 인정해야 한다는 결론이 나온다. (여기서, 수락자가 인정할 복수의 제안들을 구분하기 위해 제안마다 번호를 붙인다.) 우리는 합의되는 제안 값들이 동일하다는 가정 하에 제안을 여러 번 합의할 수 있다. 귀납법을 통해 다음 조건을 도출한다.

조건 2. 어떠한 제안이 합의되었다면, 이후 합의된 제안들은 이와 동일해야 한다.

여기서 이후라는 뜻은 제안번호가 기존의 제안번호보다 크다는 것을 뜻한다.

조건 2a. 어떠한 제안이 합의되었다면, 이후 인정된 제안들은 이와 동일해야 한다.

하지만, 아무런 제안을 받지 못한 수락자가 있는데, 전혀 다른 제안을 받는다면 어떻게 해야 하는가. 조건 1을 만족시키기 위해서는 이 제안을 수락하여야 하지만 이는 조건 2a에 반한다. 이 문제를 풀기 위하여 우리는 조건을 강화한다.

조건 2b. 어떠한 제안이 합의되었다면, 이후 제시된 제안들은 이와 동일해야 한다.
조건 2c. 과반수의 수락자들이 제안을 인정한 적이 없다면 (그 제안이 합의되지 않았다면), 제안자는 새로운 제안을 제시할 수 있다. 그렇지 않은 경우, 제안자는 임의의 과반수 수락자들이 인정안 제안 중 최신의 것을 제시하여야 한다. (왜냐하면 그것이 이미 합의된 제안일 가능성이 있기 때문에.)

단어 번역
concensus 합의
propose 제시
choose 합의
proposal 제안
prepare phase 제안번호상정
promise phase 제안번호인정
accept phase 제안상정
accepted phase 제안인정

참고문헌
Lamport, 2001, Paxos Made Simple