Доказательство. По существу, маркер передается по тем же самым каналам, как и в Алгоритме 6.14, за исключением того, что пропускается передача по листовым каналам. Т.к. передача по листовым каналам не влияет на конечное значение fatherp для любого процесса p, то в результате всегда получается дерево, которое может получиться и в Алгоритме 6.14.

Маркер последовательно проходит дважды через каждый из N-1 каналов дерева, на что тратится 2N-2 единиц времени. В каждой вершине маркер простаивает перед тем, как быть переданным, не более одного раза из-за обмена сообщениями <vis>/<ack>, что приводит к задержке не более чем на 2 единицы времени в каждой вершине.

Каждое листовое ребро передает два сообщения <vis> и два сообщения <ack>. Каждое ребро в дереве передает два сообщения <tok>, одно <vis> (посылаемое от родителя потомку), и одно <ack> (от потомка родителю). Следовательно, передается 4|E| сообщений.

var  usedp[q]      : boolean     init  false для всех q Î Neighp ;

                                             (* Признак того, отправил ли p сообщение q *)

       fatherp         : process      init udef ;

Для инициатора (выполняется один раз):

          begin   fatherp := p ;  выбор  q Î Neighp ;

                     forall  r Î Neighp  do  send <vis>  to r ;

                     forall  r Î Neighp  do  receive <ack>  from r ;

                     usedp[q] := true ;  send <tok>  to q ;

          end

Для каждого процесса при получении <tok> от q0:

          begin   if  fatherp = udef  then 

                          begin  fatherp := q0 ;

                                      forall  r Î Neighp\ {fatherp}  do  send <vis>  to r ;

                                      forall  r Î Neighp\ {fatherp}  do  receive <ack>  from r ;

                          end ;

                     if  p - инициатор  and  "q Î Neighp : usedp[q]

                        then  decide

                        else  if  $q Î Neighp : (q ¹ fatherp  &  Øusedp[q])

                                    then  begin  if  fatherp ¹ q0  &  Øusedp[q0]

                                                           then q := q0

                                                           else  выбор  q Î Neighp \ {fatherp} 

                                                                                            с Øusedp[q] ;

                                                       usedp[q] := true ;  send <tok>  to q

                                             end

                                    else  begin  usedp[fatherp] := true ;

                                                      send <tok>  to fatherp

                                             end

          end

Для каждого процесса при получении <vis> от q0:

          begin   usedp[q0] := true ;  send <ack>  to q0  end

Алгоритм 6.15 Алгоритм поиска в глубину Авербаха.

Передачу сообщения <vis> соседу, которому процесс передает маркер, можно опустить. Это усовершенствование (не выполняемое в Алгоритме 6.15) сберегает по два сообщения для каждого ребра дерева и, следовательно, уменьшает сложность сообщений на 2N-2 сообщения.

Решение Сайдона.  Алгоритм Сайдона [Cidon; Cid88] улучшает временную сложность алгоритма Авербаха, не посылая сообщения <ack>. В модификации Сайдона маркер передается немедленно, т.е. без задержки на 2 единицы времени, внесенной в алгоритм Авербаха ожиданием подтверждения. Этот же алгоритм был предложен Лакшмананом и др. [Lakshmanan; LMT87]. В алгоритме Сайдона может возникнуть следующая ситуация. Процесс p получил маркер и послал сообщение <vis> своему соседу r. Маркер позже попадает в r, но в момент, когда r получает маркер, сообщение <vis> процесса p еще не достигло r. В этом случае r может передать маркер p, фактически посылая его через листовое ребро. (Заметим, что сообщения <ack> в алгоритме Авербаха предотвращают возникновение такой ситуации.)

Чтобы обойти эту ситуацию процесс p запоминает (в переменной mrsp), какому соседу он переслал маркер в последний раз. Когда маркер проходит только по ребрам дерева, p получает его в следующий раз от того же соседа mrsp. В ситуации, описанной выше, p получает сообщение <tok> от другого соседа, а именно, от r; в этом случае маркер игнорируется, но p помечает ребро rp, как пройденное, как если бы от r было получено сообщение <vis>. Процесс r получает сообщение <vis> от p после пересылки маркера p, т.е. r получает сообщение <vis> от соседа mrsr. В этом случае r действует так, как если бы он еще не послал маркер p; r выбирает следующего соседа и передает маркер; см. Алгоритм 6.16/6.17.

Теорема 6.35  Алгоритм Сайдона (Алгоритм 6.16/6.17) вычисляет DFS-дерево за 2N-2 единиц времени, используя 4|E| сообщений.

Доказательство.  Маршрут маркера подобен маршруту в Алгоритме 6.14. Прохождение по листовым ребрам либо пропускается (как в Алгоритме 6.15), либо в ответ на маркер через листовое ребро посылается сообщение <vis>. В последнем случае, процесс, получая сообщение <vis>, продолжает передавать маркер, как если бы маркер был возвращен через листовое ребро немедленно.

Время между двумя успешными передачами маркера по дереву ограничено одной единицей времени. Если маркер послали по ребру дерева процессу p в момент времени t, то в момент t все сообщения <vis> ранее посещенных соседей q процесса p были посланы, и, следовательно, эти сообщения прибудут не позднее момента времени t+1. Итак, хотя p мог несколько раз послать маркер по листовым ребрам до t+1, не позднее t+1  p восстановился после всех этих ошибок и передал маркер по ребру, принадлежащему  дереву. Т.к. должны быть пройдены 2N-2 ребра дерева, алгоритм завершается за 2N-2 единиц времени.

Через каждый канал передается не более двух сообщений <vis> и двух <tok>, откуда граница сложности сообщений равна 4|E|.

var  usedp[q]      : boolean     init  false для всех q Î Neighp ;

       fatherp         : process      init  udef ;

       mrsp            : process      init  udef ;

Для инициатора (выполняется один раз):

          begin   fatherp := p ;  выбор  q Î Neighp ;

                     forall  r Î Neighp  do  send <vis>  to r ;

                     usedp[q] := true ;  mrsp := q ;  send <tok>  to q ;

          end

Для каждого процесса при получении <vis> от q0:

          begin   usedp[q0] := true ; 

                     if  q0 = mrsp  then  (* интерпретировать, как <tok> *)

                          передать сообщение <tok> как при получении <tok>

          end

Алгоритм 6.16 Алгоритм поиска в глубину Сайдона (Часть 1).

Для каждого процесса при получении <tok> от q0:

          begin   if mrsp ¹ udef  and  mrsp ¹ q0

                        (* это листовое ребро, интерпретируем как сообщение <vis>*)

                        then usedp[q0] := true

                        else (* действовать, как в предыдущем алгоритме *)

                            begin  if  fatherp = udef  then 

                                           begin  fatherp := q0 ;

                                                     forall  r Î Neighp\ {fatherp} 

                                                           do  send <vis>  to r ;

                                           end ;

                                        if  p - инициатор  and  "q Î Neighp : usedp[q]

                                             then  decide

                                             else  if  $q Î Neighp : (q ¹ fatherp  &  Øusedp[q])

                                                         then  begin  if  fatherp ¹ q0  &  Øusedp[q0]

                                                                                then q := q0

                                                                                else  выбор  q Î Neighp\ {fatherp} 

                                                                                                   с Øusedp[q] ;

                                                                              usedp[q] := true ;  mrsp := q ;

                                                                              send <tok>  to q

                                                                    end

                                                         else  begin  usedp[fatherp] := true ;

                                                                            send <tok>  to fatherp

                                                                  end

                            end

          end

Алгоритм 6.17 Алгоритм поиска в глубину Сайдона (Часть 2).

Во многих случаях этот алгоритм будет пересылать меньше сообщений, чем алгоритм Авербаха. Оценка количества сообщений в алгоритме Сайдона предполагает наихудший случай, а именно, когда маркер пересылается через каждое листовое ребро в обоих направлениях. Можно ожидать, что сообщения <vis> помогут избежать многих нежелательных пересылок, тогда через каждый канал будет передано только два или три сообщения.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90