Алгоритм Чанга и Робертса

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

Алгоритм

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

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

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

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

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

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

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

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

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

См. также

Ссылки

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

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

[1]