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

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

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

Рекомендации

  • Хиршберг, Д.С.; Синклер, Дж. Б. (ноябрь 1980 г.), "Децентрализованное нахождение экстремумов в круговых конфигурациях процессоров", Коммуникации ACM, 23 (11): 627–628, Дои:10.1145/359024.359029
  • Линч, Нэнси А. (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