Алгоритм Хиршберга – Синклера

Алгоритм Хиршберга -Синклера — это распределенный алгоритм, разработанный для решения задачи выбора лидера в синхронной кольцевой сети . Он назван в честь своих изобретателей Дэна Хиршберга и Дж. Б. Синклера .

Алгоритм требует использования уникальных идентификаторов (UID) для каждого процесса. Алгоритм работает поэтапно и отправляет свой UID в обоих направлениях. Сообщение передается на расстояние 2 ^{Номер фазы} прыжков, а затем сообщение возвращается к исходному процессу. Пока сообщения отправляются «исходяще», каждый принимающий процесс будет сравнивать входящий UID со своим собственным. Если UID больше, чем его собственный UID, сообщение продолжится. В противном случае, если UID меньше его собственного UID, он не будет передавать информацию. В конце фазы процесс может определить, будет ли он отправлять сообщения в следующем раунде, если он получил оба входящих сообщения. Фазы продолжаются до тех пор, пока процесс не получит оба своих исходящих сообщения от обоих своих соседей. В это время процесс знает, что это самый большой UID в кольце, и объявляет себя лидером.

Ссылки

• Хиршберг, Д.С. ; Синклер, Дж. Б. (ноябрь 1980 г.), «Децентрализованный поиск экстремумов в круговых конфигурациях процессоров», Communications of the ACM , 23 (11): 627–628, doi : 10.1145/359024.359029 , S2CID   15299430
• Линч, Нэнси А. (1996), «15.1.2 Алгоритм HS», Распределенные алгоритмы , Morgan Kaufmann Publishers, Inc., стр. 482–483, ISBN  9780080504704
• Тел, Джерард (2000), Введение в распределенные алгоритмы , Cambridge University Press, стр. 232–233, ISBN  9780521794831
• Гарг, Виджей К. (2002), «9.4 Алгоритм Хиршберга – Синклера», Элементы распределенных вычислений , John Wiley & Sons, стр. 111–112, ISBN  9780471036005