(2) Для каждого посещаемого процесса p все каналы, инцидентные p были пройдены один раз в каждом направлении. Предположив, что это не так, выберем в качестве p первый встретившийся процесс, для которого это не выполняется, и заметим, что из пункта (1) p не является инициатором. Из выбора p, все каналы, инцидентные fatherp были пройдены один раз в обоих направлениях, откуда следует, что p переслал маркер своему родителю. Следовательно, p использовал все инцидентные каналы, чтобы переслать маркер; но, т.к. маркер в конце остается в инициаторе, p получил маркер ровно столько же раз, сколько отправил его, т.е. p получил маркер по одному разу через каждый инцидентный канал. Мы пришли к противоречию.
(3) Все процессы были посещены и каждый канал был пройден по одному разу в обоих направлениях. Если есть непосещенные процессы, то существуют соседи p и q такие, что p был посещен, а q не был. Это противоречит тому, что все каналы p были пройдены в обоих направлениях. Следовательно, из пункта (2), все процессы были посещены и все каналы пройдены один раз в обоих направлениях.
Каждое вычисление алгоритма Тарри определяет остовное дерево сети, как показано в Лемме 6.3. В корне дерева находится инициатор, а каждый не-инициатор p в конце вычисления занес своего родителя в дереве в переменную fatherp. Желательно, чтобы каждый процесс также знал (в конце вычисления), какие из его соседей являются его сыновьями в дереве. Этого можно достигнуть, посылая родителю fatherp специальное сообщение.
6.4 Временная сложность: поиск в глубину
Процессы в алгоритме Тарри достаточно свободны в выборе соседа, которому передается маркер, в результате чего возникает большой класс остовных деревьев. В этом разделе будут обсуждаться алгоритмы, которые вычисляют остовные деревья с дополнительным свойством: каждое листовое ребро соединяет две вершины, одна из которых является предком другой. Листовое ребро - это ребро, не принадлежащее остовному дереву. В данном корневом остовном дереве T сети G для каждого p T[p] обозначает множество процессов в поддереве p, а A[p] обозначает предков p, т.е. вершины на пути в T от корня до p. Заметим, что q Î T[p] Û p Î A[q].
Определение 6.30 Остовное дерево T сети G называется деревом поиска в глубину, если для каждого листового ребра pq q Î T[p] Ú q Î A[p].
Деревья поиска в глубину, или DFS-деревья (DFS - Depth-First Search), используются во многих алгоритмах на графах, таких как проверка планарности, проверка двусвязности, и для построения интервальных схем маркировки (см. Подраздел 4.4.2). В Разделе 6.4.1 будет показано, что незначительная модификация алгоритма Тарри (а именно, ограничение свободы выбора процессов) позволяет алгоритму вычислять деревья поиска в глубину. Получившийся алгоритм будем называть классическим алгоритмом поиска в глубину. В Подразделе 6.4.2 будут представлены два алгоритма, которые вычисляют деревья поиска в глубину за меньшее время, чем классический алгоритм. Понятие временной сложности распределенных алгоритмов будет определено ниже. В Подразделе 6.4.3 будет представлен алгоритм поиска в глубину для сетей с начальным знанием идентификации соседей. В этом случае Теорема 6.6 неприменима, и фактически может быть дан алгоритм, использующий только 2N-2 сообщений.
Временная сложность распределенных алгоритмов. Исключительно в целях анализа распределенных алгоритмов, будут сделаны некоторые идеализированные временные предположения. Корректность алгоритмов никак не зависит от этих предположений.
Определение 6.31 Временная сложность распределенного алгоритма - это максимальное время, требуемое на вычисление алгоритма при следующих предположениях:
T1. Процесс может выполнить любое конечное количество событий за нулевое время.
T2. Промежуток времени между отправлением и получением сообщения - не более одной единицы времени.
Временные сложности всех волновых алгоритмов этой главы изложены в Таблице 6.19. Проверка величин из этой таблицы, не доказанных в этой главе, оставлена читателю в качестве упражнения. Альтернативные определения временной сложности обсуждаются в Подразделе 6.5.3.
Лемма 6.32 Для алгоритмов обхода временная сложность равна сложности сообщений.
Доказательство. Сообщения пересылаются последовательно, и каждое может занять одну единицу времени.
6.4.1 Распределенный поиск в глубину
Классический алгоритм поиска в глубину получается, когда свобода выбора соседа для передачи маркера в алгоритме Тарри ограничивается следующим, третьим правилом; см. Алгоритм 6.14.
R3. Когда процесс получает маркер, он отправляет его обратно через тот же самый канал, если это позволяется правилами R1 и R2.
Теорема 6.33 Классический алгоритм поиска в глубину (Алгоритм 6.14) вычисляет остовное дерево поиска в глубину, используя 2|E| сообщений и 2|E| единиц времени.
Доказательство. Т.к. алгоритм реализует алгоритм Тарри, это алгоритм обхода и он вычисляет остовное дерево T. Уже было показано, что каждый канал передает два сообщения (по одному в обоих направлениях), что доказывает оценку сложности сообщений, а оценка для временной сложности следует из того, что 2|E| сообщений передаются одно за другим, причем каждое занимает не более одной единицы времени. Остается показать, что из правила R3 следует, что получающееся дерево - дерево поиска в глубину.
Во-первых, из R3 следует, что за первым проходом по листовому ребру немедленно следует второй, в обратном направлении. Пусть pq - листовое ребро и p первым использует ребро. Когда q получает маркер от p, q уже посещен (иначе q присвоит fatherq p и ребро не будет листовым) и usedp[q] = false (т.к. по предположению p первый из двух процессов использовал ребро). Следовательно, по правилу R3, q немедленно отправляет маркер обратно p.
Теперь можно показать, что если pq - листовое ребро, используемое сначала p, то q Î A[p]. Рассмотрим путь, пройденный маркером, пока он не был переслан через pq. Т.к. pq - листовое ребро, q был посещен до того, как маркер попал в q через это ребро:
..., q, ..., p, q
Получим из этого пути возможно более короткий путь, заменив все комбинации r1, r2, r1, где r1r2 - листовое ребро, на r1. Из предыдущих наблюдений, все листовые ребра теперь убраны, откуда следует, что получившийся путь - это путь в T, состоящий только из ребер, пройденных до первого прохождения pq. Если q не является предком p, то отсюда следует, что ребро от q до fatherq было пройдено до того, как было пройдено ребро qp, что противоречит правилу R2 алгоритма.
var usedp[q] : boolean init false для всех q Î Neighp ;
(* Признак того, отправил ли p сообщение q *)
fatherp : process init udef ;
Для инициатора (выполняется один раз):
begin fatherp := p ; выбор q Î Neighp ;
usedp[q] := true ; send <tok> to q ;
end
Для каждого процесса при получении <tok> от q0:
begin if fatherp = udef then fatherp := q0 ;
if "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
Алгоритм 6.14 Классический алгоритм поиска в глубину.
Сложность сообщений классического распределенного поиска в глубину равна 2|E|, по Теореме 6.6 это наилучшая сложность (за исключением множителя 2), если идентификация соседей не известна изначально. Временная сложность также составляет 2|E|, что по Лемме 6.32, является наилучшей сложностью для алгоритмов обхода в этом случае. Распределенная версия поиска в глубину была впервые представлена Cheung [Che83].
В Подразделе 6.4.2 будут рассмотрены два алгоритма, которые строят дерево поиска в глубину в сети без знания идентификации соседей за O(N) единиц времени. Следовательно, эти алгоритмы не являются алгоритмами обхода. В Подразделе 6.4.3 знание о соседях будет использовано для получения алгоритма с временной сложностью и сложностью сообщений O(N).
6.4.2 Алгоритмы поиска в глубину за линейное время
Причина высокой временной сложности классического алгоритма поиска в глубину состоит в том, что все ребра, как принадлежащие дереву, так и листовые, обходятся последовательно. Сообщение-маркер <tok> проходит по всем листовым ребрам и немедленно возвращается обратно, как показано в доказательстве Теоремы 6.33. Все решения с меньшей временной сложностью основаны на том, что маркер проходит только по ребрам дерева. Очевидно, на это потребуется линейное время, т.к. существует только N-1 ребро дерева.
Решение Авербаха. В алгоритм включается механизм, который предотвращает передачу маркера через листовое ребро. В алгоритме Авербаха [Awerbuch; Awe85b] гарантируется, что каждый процесс в момент, когда он должен передать маркер, знает, какие из его соседей уже были пройдены. Затем процесс выбирает непройденного соседа, или, если такого не существует, посылает маркер своему родителю.
Когда процесс p впервые посещается маркером (для инициатора это происходит в начале алгоритма), p сообщает об этом всем соседям r, кроме его родителя, посылая сообщения <vis>. Передача маркера откладывается, пока p не получит сообщения <ack> от всех соседей. При этом гарантируется, что каждый сосед r процесса p в момент, когда p передает маркер, знает, что p был посещен. Когда позже маркер прибывает в r, r не передаст маркер p, если только p не его родитель; см. Алгоритм 6.15.