Алгоритм Чанга и Робертса - Chang and Roberts algorithm

В Алгоритм Чанга и Робертса[1] это кольцевой алгоритм выбора координатора, работает в распределенных вычислений.

Алгоритм

Алгоритм предполагает, что каждый процесс имеет уникальный идентификатор (UID) и что процессы могут быть организованы в однонаправленное кольцо с каналом связи, идущим от каждого процесса к соседу по часовой стрелке. Двухчастный алгоритм можно описать следующим образом:

  1. Первоначально каждый процесс в кольце отмечен как неучастник.
  2. Процесс, который замечает отсутствие лидера, запускает выборы. Это создает сообщение о выборах содержащий его UID. Затем он отправляет это сообщение своему соседу по часовой стрелке.
  3. Каждый раз, когда процесс отправляет или пересылает сообщение о выборах, процесс также отмечает себя участником.
  4. Когда процесс получает сообщение о выборах он сравнивает UID в сообщении со своим собственным UID.
    1. Если UID в сообщении о выборах больше, процесс безоговорочно пересылает сообщение о выборах по часовой стрелке.
    2. Если UID в сообщении о выборах меньше, а процесс еще не является участником, процесс заменяет UID в сообщении своим собственным UID, отправляет обновленный сообщение о выборах по часовой стрелке.
    3. Если UID в сообщении о выборах меньше, а процесс уже участник (т.е. процесс уже отправил сообщение о выборах с UID, по крайней мере, таким же большим, как его собственный UID), процесс отбрасывает сообщение о выборах.
    4. Если UID во входящем сообщении о выборах совпадает с UID процесса, этот процесс начинает действовать как лидер.

Когда процесс начинает действовать как лидер, начинается второй этап алгоритма.

  1. Лидерский процесс отмечает себя как неучастник и отправляет избранное сообщение своему соседу, объявляющему о своем избрании и UID.
  2. Когда процесс получает избранное сообщение, он отмечает себя как неучастник, записывает выбранный UID и пересылает избранное сообщение без изменений.
  3. Когда избранное сообщение достигает вновь избранного лидера, лидер отбрасывает это сообщение, и выборы окончены.

Предполагая, что ошибок нет, этот алгоритм завершится. Алгоритм работает для любого количества процессов N и не требует, чтобы какой-либо процесс знал, сколько процессов находится в кольце.

Характеристики

Алгоритм уважает безопасность: процесс получит выбранное сообщение со своим собственным UID, только если его UID больше, чем у других, и только тогда, когда все процессы согласятся на один и тот же UID. Алгоритм также учитывает живость. Состояния «участник» и «не участник» используются таким образом, что, когда несколько процессов начинают выборы примерно в одно и то же время, будет объявлен только один победитель.

Когда выборы запускает один процесс, алгоритм требует в худшем случае 3N-1 последовательных сообщений. В худшем случае процесс, запускающий выборы, следует сразу за процессом с наибольшим UID: ему требуется N-1 сообщений, чтобы сообщение о выборах достигло его, затем N сообщений, чтобы он получил свой собственный UID, затем другие N сообщений послать всем в кольце избранное сообщение.

Этот алгоритм не очень отказоустойчив. Отказоустойчивость можно повысить, если каждый процесс знает всю топологию, путем введения сообщений ACK и пропуска неисправных узлов при отправке сообщений.

Смотрите также

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

  1. ^ Эрнест Чанг; Розмари Робертс (1979), «Улучшенный алгоритм децентрализованного поиска экстремумов в круговых конфигурациях процессов», Коммуникации ACM, ACM, 22 (5): 281–283, Дои:10.1145/359104.359108CS1 maint: несколько имен: список авторов (связь)