Chang 및 Roberts 알고리즘

Chang and Roberts algorithm

Chang and Roberts[1] 알고리즘은 링 기반의 코디네이터 선택 알고리즘으로 분산 컴퓨팅에 사용됩니다.

알고리즘

알고리즘에서는 각 프로세스가 Unique Identification(UID; 고유 식별)을 가지며 각 프로세스에서 시계방향 네이버로 가는 통신채널을 가진 단일방향 링으로 프로세스 자체를 배치할 수 있다고 가정합니다.두 부분 알고리즘은 다음과 같이 설명할 수 있습니다.

  1. 처음에 링 내의 각 프로세스는 비참여자로 표시됩니다.
  2. 리더가 부족하다는 것을 알아차린 과정이 선거를 시작합니다.UID가 포함된 선거 메시지가 생성됩니다.그런 다음 이 메시지를 시계 방향으로 인접 라우터에 보냅니다.
  3. 프로세스가 선거 메시지를 전송 또는 전송할 때마다 프로세스 자체도 참여자로 표시됩니다.
  4. 프로세스는 선택 메시지를 수신하면 메시지 내의 UID를 자체 UID와 비교합니다.
    1. 선거 메시지의 UID가 클 경우 프로세스는 무조건 시계 방향으로 선거 메시지를 전송합니다.
    2. 선택 메시지 내의 UID가 작고 프로세스가 아직 참가자가 아닌 경우 프로세스는 메시지 내의 UID를 자체 UID로 대체하고 업데이트된 선택 메시지를 시계 방향으로 보냅니다.
    3. 선거 메시지 내의 UID가 작고 프로세스가 이미 참가자인 경우(즉, 프로세스가 자신의 UID만큼 큰 UID를 가진 선거 메시지를 이미 발송한 경우) 프로세스는 선거 메시지를 폐기합니다.
    4. 착신 선택 메시지 내의 UID가 프로세스의 UID와 같은 경우, 그 프로세스는 리더로서 기능하기 시작합니다.

프로세스가 리더로서 동작하기 시작하면 알고리즘의 두 번째 단계가 시작됩니다.

  1. 리더 프로세스는 자신을 비참여자로 마크하고 선출 및 UID를 알리는 선출된 메시지를 인접 라우터에 보냅니다.
  2. 프로세스는 선택된 메시지를 수신하면 자신을 비참여자로 마크하고 선택된 UID를 기록하고 선택된 메시지를 변경하지 않고 전송합니다.
  3. 선출된 메시지가 새로 선출된 리더에 도달하면 리더는 해당 메시지를 폐기하고 선거는 종료됩니다.

장애가 없다고 가정하면 이 알고리즘은 종료됩니다.이 알고리즘은 임의의 수의 프로세스N에 대해 기능하며 링 내에 몇 개의 프로세스가 있는지 알기 위해 어떤 프로세스도 필요하지 않습니다.

특성.

이 알고리즘은 안전성을 존중합니다.프로세스가 자신의 UID가 다른 UID보다 큰 경우에만, 그리고 모든 프로세스가 동일한 UID에 동의하는 경우에만 프로세스가 자체 UID로 선택된 메시지를 수신합니다.이 알고리즘은 라이브도 존중합니다."참가자" 및 "참가자가 아님" 상태는 여러 프로세스가 선거를 거의 동시에 시작할 때 단일 당선자만 발표되도록 사용됩니다.

선거를 시작하는 단일 프로세스가 있는 경우 알고리즘은 최악의 경우 3N-1 순차 메시지를 요구합니다.최악의 경우로는 선출을 시작하는 프로세스가 UID가 가장 큰 프로세스 바로 다음에 이어지는 경우입니다.선택 메시지가 도달하려면 N-1 메시지가 필요하고, 그 후 N 메시지가 반환되어 자신의 UID가 반환되고, 그 외의 N 메시지가 호출음 내의 모든 사용자에게 선택 메시지를 보냅니다.

이 알고리즘은 폴트 톨러런스가 별로 없습니다.모든 프로세스가 토폴로지 전체를 인식하고 있는 경우 ACK 메시지를 도입하고 메시지 전송 시 장애가 있는 노드를 건너뛰면 폴트 톨러런스를 높일 수 있습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Ernest Chang; Rosemary Roberts (1979), "An improved algorithm for decentralized extrema-finding in circular configurations of processes", Communications of the ACM, ACM, 22 (5): 281–283, doi:10.1145/359104.359108{{citation}}: CS1 maint: 여러 이름: 작성자 목록(링크)