Алгоритмы выбора для кольцевых архитектур

В алгоритме Лелана для распределенной системы с архитектурой кольца (ориентированного цикла) каждый инициатор вычисляет список идентификаторов всех инициаторов, после чего выбирается инициатор с наибольшей оценкой est (). Каждый инициатор посылает маркер, содержащий его идентификатор, по кольцу, и этот маркер передается всеми сайтами. Предполагается, что каналы подчиняются дисциплине FIFO, и что инициатор должен сгенерировать свой маркер до того, как он получит маркер другого инициатора (когда сайт получает маркер, он после этого не инициирует алгоритм).

Когда инициатор p получает свой собственный маркер, маркеры всех инициаторов прошли через p, и p выбирается лишь в том случае, если p имеет наибольшую оценку среди инициаторов. Напоминаем, что нужно различать внешнее и внутреннее обозначения сайтов. Здесь p и q – внешние обозначения. Они используются при необходимости процессами, выполняющимися на других сайтах. Собственный сайт p в своем процессе обозначается идентификатором this. При этом, разумеется, p и this имеют одно и то же значение (например, числовое или код). В приведенном ниже алгоритме переменная state задает состояние сайта.

Алгоритм Лелана:

var List_p: set of integer init { est (this)};

state: (sleep, coordinator, lost);

Begin ifthis - инициатор then

begin state:= cand; send (token, this) to Next_p; receive (token, q);

Whileq ¹ this do

begin List_p:= List_p È {q};

send (token, q) to Next_p; receive (token, q);

end;

if this = max (List_p) then state:= coordinator

else state:= lost

End

else repeat receive (token, q); send (token, q) to Next_p;

if state = sleep then state:= lost

until false

End

Так как порядок маркеров в кольце сохраняется (из предположения о каналах FIFO), и инициатор q отправляет (token, q) до того какполучит (token, p), то инициатор p получает (token, q) прежде, чем вернется (token, p). Отсюда следует, что каждый инициатор p заканчивается со списком List_p, совпадающим с множеством всех инициаторов, и единственным выбираемым сайтом становится инициатор с наибольшей оценкой.

Все не-инициаторы приходят в состояние проигравший, но навсегда остаются в ожидании сообщений (token, r). Ожидание может быть прервано, если лидер посылает по кольцу специальный маркер, чтобы объявить об окончании выборов.

Алгоритм Чанга-Робертса, приведенный ниже, устраняет из кольца маркеры тех сайтов, для которых очевидно, что они проиграют выборы. В этом смысле он улучшает алгоритм Лелана. Т.е. инициатор p удаляет из кольца маркер (token, q), если est (q) < est (p). Инициатор p становится проигравшим, когда получает маркер с идентификатором q, таким что est (q) > est (p), или координатором, когда он получает маркер с идентификатором p.

var state: (sleep, coordinator, lost);