Лекция: Begin ifthis - инициатор then

beginis_sent := true ;

forallq Î Out(this) dosend <wakeup> to q

end ;

While counter < card(Out(this)) do

beginreceive <wakeup>; counter := counter + 1 ;

If notis_sent then

beginis_sent := true ;

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

End

end ;

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

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

beginreceive (token, r) from q; recp[q] := true ;

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

end;

send (token, m) to q0with Ørecp[q0] ;

receive (token, r) from q0;

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

ifm = this thenstate := coordinator elsestate := lost ;

forallq Î Out(this), q ¹ q0dosend (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), прибывающие позднее.