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

begin is_sent:= true;

forall q Î Out(this) do send < wakeup > to q

end;

While counter < card(Out(this)) do

begin receive < wakeup >; counter:= counter + 1;

If notis_sent then

begin is_sent:= true;

forall q Î Out(this) do send < wakeup > to q

End

end;

(* Начало алгоритма из лекции 12 *)

Whilecard{q: Ørecp[q]} > 1 do

begin receive (token, r) from q; rec_p[q]:= true;

if est (r) > est (m) then m:= r

end;

send (token, m) to q₀ with Ørec_p[q₀];

receive (token, r) from q₀;

if est (r) > est (m) then m:= r; (* return (OK)с ответом m *)

if m = this then state:= coordinator else state:= lost;

forall q Î Out(this), q ¹ q₀ do send (token, m) to q

End

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

Через каждый канал пересылается по два сообщения < wakeup > и по два сообщения < tok,r>, откуда сложность сообщений равна 4N–4. В течение D единиц времени после того, как первый процесс начал алгоритм, каждый процесс послал сообщения < wakeup >, следовательно, в течение D+1 единиц времени каждый процесс начал волну. Легко заметить, что первое решение принимается не позднее, чем через D единиц времени после начала волны, а последнее решение принимается не позднее D единиц времени после первого, откуда полное время равно 3D+1.

Если порядок сообщений в канале может быть изменен (т.е. канал – не FIFO), процесс может получить сообщение (token, r) от соседа прежде чем он получил сообщение < wakeup > от этого соседа. В этом случае сообщение (token, r) может быть временно сохранено или обработано как сообщения (token, r), прибывающие позднее.