Если топология распределенной системы – дерево или доступно остовное дерево системы, выбор можно провести с помощью алгоритма, приведенного в лекции 12. В этом алгоритме требуется, чтобы все концевые вершины были инициаторами алгоритма. Чтобы преобразовать алгоритм на случай, когда некоторые сайты также являются инициаторами, добавляется фаза wake-up. Сайты, которые хотят начать выборы, рассылают сообщение <wakeup> всем другим сайтам.
Когда сайт получит сообщение <wakeup> через каждый канал, он начинает выполнять алгоритм из лекции 12, который расширен таким образом, чтобы вычислять идентификатор сайта с наибольшей оценкой, и чтобы каждый сайт выполнял процедуру return(OK). Когда сайт выполняет эту процедуру, он знает идентификатор координатора; если этот идентификатор совпадает с идентификатором процесса, он становится координатором, а если нет – проигравшим.
В тексте алгоритма логическая переменная sent («отправлено») используется, чтобы каждый сайт послал сообщения <wakeup> не более одного раза, а переменная counter (счетчик) используется для подсчета количества сообщений <wakeup>, полученных сайтом.
var is_sent : boolean init false ;
counter: integer init 0 ;
recp[q] : boolean для всех q Î Out(this) init false ;
m : integer init this ;
state : (sleep, coordinator, lost) init sleep ;