Выбор с помощью алгоритма для деревьев

Если топология распределенной системы – дерево или доступно остовное дерево системы, выбор можно провести с помощью алгоритма, приведенного в лекции 12. В этом алгоритме требуется, чтобы все концевые вершины были инициаторами алгоритма. Чтобы преобразовать алгоритм на случай, когда некоторые сайты также являются инициаторами, добавляется фаза wake-up. Сайты, которые хотят начать выборы, рассылают сообщение < wakeup > всем другим сайтам.

Когда сайт получит сообщение < wakeup > через каждый канал, он начинает выполнять алгоритм из лекции 12, который расширен таким образом, чтобы вычислять идентификатор сайта с наибольшей оценкой, и чтобы каждый сайт выполнял процедуру return (OK). Когда сайт выполняет эту процедуру, он знает идентификатор координатора; если этот идентификатор совпадает с идентификатором процесса, он становится координатором, а если нет – проигравшим.

В тексте алгоритма логическая переменная sent («отправлено») используется, чтобы каждый сайт послал сообщения < wakeup > не более одного раза, а переменная counter (счетчик) используется для подсчета количества сообщений < wakeup >, полученных сайтом.

var is_sent: boolean init false;

counter: integer init 0;

rec_p[q]: boolean для всех q Î Out(this) init false;

m: integer init this;

state: (sleep, coordinator, lost) init sleep;