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

Алгоритм Хуанга — це алгоритм виявлення зупинень в розподіленій системі. Алгоритм був запропонований Шинг-Цааном Хуан у 1989 р. в «Journal of Computers».

У розподіленій системі процес в будь-який момент часу знаходиться або в активному стані або в режимі очікування. Зупинення відбувається коли всі процеси стають непрацездатними і немає жодного транзитного (на шляху його доставки) обчислювального повідомлення.

Алгоритм включає такі правила

• Один із взаємодіючих процесів, який контролює обчислення, називається контрольним агентом.
• Початкова маса контролюючого агента становить 1
• Усі інші процеси спочатку простоюють і мають вагу 0.
• Обчислення починається, коли керуючий агент надсилає обчислювальне повідомлення одному з процесів.
• Процес стає активним при отриманні обчислювального повідомлення.
• Повідомлення обчислень може надсилатися тільки контрольним агентом або активним процесом.
• Повідомлення управління надсилається контрольному агенту активним процесом, коли вони стають непрацюючими.
• Алгоритм призначає вагу W (такий, що 0 <W <1) кожному активному процесу і кожному транзитному повідомленню.

Переваги алгоритму Хуанга

Алгоритм виявляє кожне справжнє припинення в обмежений час.

Недоліки алгоритму Хуанга

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

Див. також

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

Зноски

1. (1989). Termination detection by using distributed snapshots. Information Processing Letters. 32 (3): 113—119. doi:10.1016/0020-0190(89)90010-0.