Реферат: Распределенные алгоритмы
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.
Из-за передачи сообщений <vis> в большинстве случаев usedp[fatherp] = true, даже если p еще не послал маркер своему родителю. Поэтому в алгоритме должно быть явно запрограммировано, что только инициатор может принимать решения; а не-инициатор p, для которого usedp[q] = true для всех соседей q, передает маркер своему родителю.
Теорема 6.34 Алгоритм Авербаха (Алгоритм 6.15) вычисляет дерево поиска в глубину за 4N-2 единиц времени и использует 4|E| сообщений.
Доказательство. По существу, маркер передается по тем же самым каналам, как и в Алгоритме 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] ;
Страницы: 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, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
