ref (664672), страница 22

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 22)

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

var used_p[q] : boolean init false для всех q  Neigh_p ;

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

father_p : process init udef ;

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

begin father_p := p ; выбор q  Neigh_p ;

forall r  Neigh_p do send <vis> to r ;

forall r  Neigh_p do receive <ack> from r ;

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

end

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

begin if father_p = udef then

begin father_p := q₀ ;

forall r  Neigh_p\ {father_p} do send <vis> to r ;

forall r  Neigh_p\ {father_p} do receive <ack> from r ;

end ;

if p - инициатор and q  Neigh_p : used_p[q]

then decide

else if q  Neigh_p : (q  father_p & used_p[q])

then begin if father_p  q₀ & used_p[q₀]

then q := q₀

else выбор q  Neigh_p \ {father_p}

с used_p[q] ;

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

end

else begin used_p[father_p] := true ;

send <tok> to father_p

end

end

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

begin used_p[q₀] := true ; send <ack> to q₀ 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 запоминает (в переменной mrs_p), какому соседу он переслал маркер в последний раз. Когда маркер проходит только по ребрам дерева, p получает его в следующий раз от того же соседа mrs_p. В ситуации, описанной выше, p получает сообщение <tok> от другого соседа, а именно, от r; в этом случае маркер игнорируется, но p помечает ребро rp, как пройденное, как если бы от r было получено сообщение <vis>. Процесс r получает сообщение <vis> от p после пересылки маркера p, т.е. r получает сообщение <vis> от соседа mrs_r. В этом случае 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 used_p[q] : boolean init false для всех q  Neigh_p ;

father_p : process init udef ;

mrs_p : process init udef ;

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

begin father_p := p ; выбор q  Neigh_p ;

forall r  Neigh_p do send <vis> to r ;

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

end

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

begin used_p[q₀] := true ;

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

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

end

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

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

begin if mrs_p  udef and mrs_p  q₀

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

then used_p[q₀] := true

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

begin if father_p = udef then

begin father_p := q₀ ;

forall r  Neigh_p\ {father_p}

do send <vis> to r ;

end ;

if p - инициатор and q  Neigh_p : used_p[q]

then decide

else if q  Neigh_p : (q  father_p & used_p[q])

then begin if father_p  q₀ & used_p[q₀]

then q := q₀

else выбор q  Neigh_p\ {father_p}

с used_p[q] ;

used_p[q] := true ; mrs_p := q ;

send <tok> to q

end

else begin used_p[father_p] := true ;

send <tok> to father_p

end

end

end

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

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

Сайдон замечает, что хотя алгоритм может передать маркер в уже посещенную вершину, он обладает лучшей временной сложностью (и сложностью сообщений), чем Алгоритм 6.15, который предотвращает такие нежелательные передачи. Это означает, что на восстановление после ненужных действий может быть затрачено меньше времени и сообщений, чем на их предотвращение. Сайдон оставляет открытым вопрос о том, существует ли DFS-алгоритм, который достигает сложности сообщений классического алгоритма, т.е. 2|E|, и который затрачивает O(N) единиц времени.

6.4.3 Поиск в глубину со знанием соседей

Если процессам известны идентификаторы их соседей, проход листовых ребер можно предотвратить, включив в маркер список посещенных процессов. Процесс p, получая маркер с включенным в него списком L, не передает маркер процессам из L. Переменная used_p[q] не нужна, т.к. если p ранее передал маркер q, то q  L; см. Алгоритм 6.18.

Теорема 6.36 DFS-алгоритм со знанием соседей является алгоритмом обхода и вычисляет дерево поиска в глубину, используя 2N-2 сообщений за 2N-2 единиц времени.

У этого алгоритма высокая битовая сложность; если w - количество бит, необходимых для представления одного идентификатора, список L может занять до Nw бит; см. Упражнение 6.14.

var father_p : process init udef ;

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

begin father_p := p ; выбор q  Neigh_p ;

send <tlist, {p}> to q

end

Для каждого процесса при получении <tlist, L> от q₀:

begin if father_p = udef then father_p := q₀ ;

if q  Neigh_p \ L

then begin выбор q  Neigh_p \ L ;

send < tlist, L{p} > to q

end

else if p - инициатор

then decide

else send < tlist, L{p} > to father_p

end

Алгоритм 6.18 Алгоритм поиска в глубину со знанием соседей.

6.5 Остальные вопросы

6.5.1 Обзор волновых алгоритмов

В Таблице 6.19 дан список волновых алгоритмов, рассмотренных в этой главе. В столбце «Номер» дана нумерация алгоритмов в главе; в столбце «C/D» отмечено, является ли алгоритм централизованным (C) или децентрализованным (D); столбец «T» определяет, является ли алгоритм алгоритмом обхода; в столбце «Сообщения» дана сложность сообщений; в столбце «Время» дана временная сложность. В этих столбцах N - количество процессов, |E| - количество каналов, D - диаметр сети (в переходах).

Замечание: фазовый алгоритм (6.7) и алгоритм Финна (6.9) подходят для ориентированных сетей.

Таблица 6.19 Волновые алгоритмы этой главы.

Сложность распространения волн в сетях большинства топологий значительно зависит от того, централизованный алгоритм или нет. В Таблице 6.20 приведена сложность сообщений централизованных и децентрализованных волновых алгоритмов для колец, произвольных сетей и деревьев. Таким же образом можно проанализировать зависимость сложности от других параметров, таких как знание соседей или чувство направления (Раздел B.3).

Таблица 6.20 Влияние централизации на сложность сообщений.

Характеристики

Список файлов реферата