황 알고리즘

Huang의 알고리즘은 분산 시스템에서 종료를 탐지하는 알고리즘입니다.이 알고리즘은 1989년 Sing-Tsaan Huang에 의해 Journal of ^[1]Computers에서 제안되었다.

종료 검출

종료 검출의 기초는 분산 시스템 프로세스 상태에 있습니다.분산 시스템의 프로세스는 항상 활성 상태 또는 유휴 상태입니다.활성 프로세스는 언제든지 유휴 상태가 될 수 있지만 유휴 프로세스는 계산 메시지를 수신한 후에만 다시 활성 상태가 될 수 있습니다.

종료는 분산 시스템 내의 모든 프로세스가 아이돌 상태가 되어 전송 중인 계산 메시지가 없을 때 발생합니다.

Huang의 알고리즘은 다음과 같이 설명할 수 있습니다.

처음에는 모든 프로세스가 아이돌 상태입니다.
분산 태스크는 계산 메시지를 다른 프로세스에 보내는 프로세스에 의해 시작됩니다.메시지를 보내는 이 초기 프로세스는 "컨트롤 에이전트"입니다.
- 제어제의 초기 $w$ 은w\ $displaystyle$ w $($ 일반적으로 1)입니다.
다음 규칙이 계산 전체에 적용됩니다.
- 메시지를 보내는 프로세스는 현재 무게를 메시지와 자체 간에 분할합니다.
- 메시지를 수신하는 프로세스는 메시지 자체의 무게를 더합니다.
- 아이돌 상태가 되면 프로세스는 자신의 무게 전체를 포함하는 메시지를 제어 에이전트에 다시 전송하고 아이돌 상태가 됩니다.
- 종료는 제어 에이전트의 무게가 $w$ \ $displaystyle$ w이고 아이돌 상태일 $w$ 때 발생합니다.

Huang 알고리즘의 약점은 메시지가 전송 중에 손실되거나 활성 상태에서 프로세스가 실패하면 종료를 감지할 수 없다는 것입니다.