찬드라Toueg 컨센서
Chandra–찬드라-1996년 투샤르 디팍 찬드라(Tushar Deepak Chandra)와 샘 투에그(Sam Toug)가 발표한 투에그 합의 알고리즘은 궁극적으로 강력한 기능 상실 검출기를 갖춘 신뢰할 수 없는 프로세스 네트워크에서 합의를 해결하기 위한 알고리즘이다.장애 검출기는 타임아웃의 추상적인 버전으로, 다른 프로세스가 크래쉬 했을 가능성이 있는 경우에 각 프로세스에 신호를 보냅니다.최종적으로 강력한 장애 검출기란 어떤 특정 비장애 프로세스가 혼란의 초기 시간 후에 실패한 것으로 식별되지 않고, 동시에 모든 장애가 발생한 프로세스를 실패로 식별하는 것입니다(불량 프로세스는 결국 실패 또는 크래쉬하는 프로세스이며, 비장애 프로세스는 실패하지 않습니다).찬드라-Toug 컨센서스 알고리즘은 다음과 같이 나타나는 결함 프로세스의 수를 가정합니다.f는 n/2 미만(소수)이다. 즉, 가정한다.f< >n/2. 여기서 n은 프로세스의 총 수입니다.
알고리즘
알고리즘은 라운드로 진행되며 각 라운드에서 회전 코디네이터를 사용합니다.r에 의해 ID가 부여되는 프로세스r모드n코디네이터로 선정되었습니다.각 프로세스는 현재 우선 결정 값(처음에는 프로세스의 입력과 동일)과 결정 값을 변경한 마지막 라운드(값의 타임스탬프)를 추적합니다.각 라운드에서 수행되는 조치는 다음과 같습니다.
- 모든 프로세스(r, 프리퍼런스, 타임스탬프)가 코디네이터로 전송됩니다.
- 코디네이터는 프로세스 절반 이상(자체 포함)에서 메시지를 수신할 때까지 대기합니다.
- 그런 다음 기본 설정으로 전송된 값 중 가장 최근의 타임스탬프를 가진 값을 선택합니다.
- 코디네이터는 (r, preference)를 모든 프로세스에 송신합니다.
- 각 프로세스는 (1) 코디네이터로부터 수신(r, preference)하거나 (2) 고장 검출기가 코디네이터가 충돌한 것으로 식별될 때까지 대기합니다.
- 첫 번째 예에서는 코디네이터의 프리퍼런스에 자신의 프리퍼런스를 설정하고 ack(r)로 응답합니다.
- 두 번째 경우 nack(r)을 코디네이터로 전송합니다.
- 코디네이터는 대부분의 프로세스에서 ack(r) 또는 nack(r)을 수신할 때까지 대기합니다.
- 과반수로부터 ack(r)을 수신하면, 모든 프로세스에 결정(프리퍼런스)을 송신합니다.
- 최초로 결정(프리퍼런스)을 수신한 프로세스는 모든 프로세스에 대해 결정(프리퍼런스)한 후 프리퍼런스를 결정하고 종료합니다.
이 알고리즘은 1개의 값만 결정하기 위해 사용됩니다.
정확성
문제의 정의
컨센서스 문제를 해결하는 알고리즘은 다음 속성을 보증해야 합니다.
- 종료: 모든 프로세스가 값을 결정합니다.
- 합의: 모든 프로세스가 동일한 가치를 결정한다.
- 타당성: 모든 프로세스가 일부 프로세스의 입력값이었던 값을 결정한다.
전제 조건
찬드라에 대해 논쟁하기 전에...Toueg 컨센서스 알고리즘은 위의 세 가지 속성을 충족합니다.이 알고리즘은 다음을 필요로 합니다.n= 2*f+ 1개의 프로세스(최대 f개)가 불량입니다.
또, 이 알고리즘은, 최종적으로 강한 고장 검출기(접근 가능하고, 노드의 크래시를 검출하기 위해서 사용할 수 있는 것)의 존재를 전제로 하고 있습니다.최종적으로 강력한 장애 검출기란, 몇개의 특정의 비장애(또는 올바른) 프로세스가, 어느 정도의 혼란이 발생한 후에, 실패했다고 특정되지 않는(또는 올바른) 프로세스를 검출하는 검출기이며, 동시에, 결과적으로 모든 장애가 발생한 프로세스를 실패라고 특정하는 검출기입니다.
정확성 증명
최종적으로 장애 검출기가 일부 비장애 프로세스 p의 의심을 중지하고 최종적으로 p가 코디네이터가 되기 때문에 종료가 유지됩니다.알고리즘이 종료되기 전에 어떤 라운드r 로 종료되지 않은 경우 라운드r 내의 모든 비장애 프로세스는 p 의 프리퍼런스를 수신할 때까지 대기하고 ack(r)로 응답합니다.이것에 의해, p는 충분한 확인 응답을 수집해, 결정(프리퍼런스)을 송신할 수 있게 되어, 모든 프로세스가 종료됩니다.또는 전송에 장애가 있는 코디네이터가 몇 가지 프로세스에만 결정을 내릴 수도 있습니다.단, 이들 프로세스 중 하나라도 장애가 없는 경우에는 나머지 모든 프로세스에 결정을 브로드캐스트하여 결정을 내리고 종료합니다.
유효성은 모든 기본 설정이 일부 프로세스의 입력으로 시작된다는 사실에서 비롯됩니다. 프로토콜에는 새로운 기본 설정을 생성하는 것이 없습니다.
합의는 잠재적으로 가장 달성하기 어려운 것이다.코디네이터는 다른 코디네이터가 다른 값 v'에 대해 다른 값 v'에 대한 결정 메시지를 보내기 전에 한 라운드의 값 v'에서 결정 메시지를 보낼 수 있습니다.이것이 발생하지 않는 것을 나타내려면 첫 번째 코디네이터가 decision(v)을 송신하기 전에 대부분의 프로세스로부터 ack(r)을 수신해야 합니다.그러나 이후 코디네이터가 대부분의 프로세스를 폴링할 때 이전 코디네이터와 겹치고 v가 최신 값이 됩니다.따라서 결정 메시지를 보내는 두 코디네이터는 동일한 값을 보냅니다.
