Алгоритм Хиршберга-Синклера - 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
Этот алгоритмы или структуры данных -связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |