Алгоритм Хуанга
Алгоритм Хуанга — це алгоритм виявлення зупинень в розподіленій системі. Алгоритм був запропонований Шинг-Цааном Хуан у 1989 р. в «Journal of Computers».[1]
У розподіленій системі процес в будь-який момент часу знаходиться або в активному стані або в режимі очікування. Зупинення відбувається коли всі процеси стають непрацездатними і немає жодного транзитного (на шляху його доставки) обчислювального повідомлення.
Алгоритм включає такі правила ред.
- Один із взаємодіючих процесів, який контролює обчислення, називається контрольним агентом.
- Початкова маса контролюючого агента становить 1
- Усі інші процеси спочатку простоюють і мають вагу 0.
- Обчислення починається, коли керуючий агент надсилає обчислювальне повідомлення одному з процесів.
- Процес стає активним при отриманні обчислювального повідомлення.
- Повідомлення обчислень може надсилатися тільки контрольним агентом або активним процесом.
- Повідомлення управління надсилається контрольному агенту активним процесом, коли вони стають непрацюючими.
- Алгоритм призначає вагу W (такий, що 0 <W <1) кожному активному процесу і кожному транзитному повідомленню.
Переваги алгоритму Хуанга ред.
Алгоритм виявляє кожне справжнє припинення в обмежений час.
Недоліки алгоритму Хуанга ред.
Алгоритм не в змозі виявити завершення обчислень, якщо повідомлення втрачено в дорозі та також не працює, коли процес не працює, перебуваючи в активному стані.
Див. також ред.
Зноски ред.
- ↑ Huang, Shing-Tsaan (1989). Termination detection by using distributed snapshots. Information Processing Letters. 32 (3): 113—119. doi:10.1016/0020-0190(89)90010-0.