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

В алгоритме Лелана для распределенной системы с архитектурой кольца (ориентированного цикла) каждый инициатор вычисляет список идентификаторов всех инициаторов, после чего выбирается инициатор с наибольшей оценкой 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);