Алгоритм Хуанга

Алгоритм Хуанга — это алгоритм обнаружения завершения в распределенной системе . Алгоритм был предложен Шинг-Цааном Хуаном в 1989 году в журнале Journal of Computers . ^{[ 1 ]}

Обнаружение завершения

В основе обнаружения завершения лежит концепция состояния процесса распределенной системы. В любой момент времени процесс в распределенной системе находится либо в активном состоянии, либо в состоянии ожидания. Активный процесс может стать бездействующим в любое время, но бездействующий процесс может снова стать активным только после получения вычислительного сообщения.

Завершение происходит, когда все процессы в распределенной системе простаивают и в пути отсутствуют вычислительные сообщения.

Алгоритм

Алгоритм Хуанга можно описать следующим образом:

Изначально все процессы простаивают.
Распределенная задача запускается процессом, отправляющим вычислительное сообщение другому процессу. Этот первоначальный процесс отправки сообщения является «контролирующим агентом».
- Начальный вес управляющего агента равен $w$ (обычно 1).
При расчете применяются следующие правила:
- Процесс, отправляющий сообщение, разделяет свой текущий вес между собой и самим сообщением.
- Процесс, получающий сообщение, добавляет к себе вес сообщения.
- При бездействии процесс отправляет сообщение, содержащее весь его вес, обратно управляющему агенту, и процесс переходит в режим ожидания.
- Прекращение действия происходит, когда контролирующий агент имеет вес $w$ и находится в состоянии ожидания.

Некоторые недостатки алгоритма Хуана заключаются в том, что он не может обнаружить завершение, если сообщение потеряно при передаче или если процесс выходит из строя в активном состоянии.

См. также

Алгоритм Дейкстры – Шолтена

Примечания

^ Хуан, Шинг-Цаан (1989). «Обнаружение завершения работы с помощью распределенных снимков» . Письма об обработке информации . 32 (3): 113–119. дои : 10.1016/0020-0190(89)90010-0 .

[1] Хуан, Шинг-Цаан (1989). «Обнаружение завершения работы с помощью распределенных снимков» . Письма об обработке информации . 32 (3): 113–119. дои : 10.1016/0020-0190(89)90010-0 .

[ 1 ]