Реферат: Распределенные алгоритмы
Для каждого процесса при получении маркера <num,k>:
begin if k=2n then decide
else begin пусть l - наибольший номер : 2l|k ;
send <num,k+1> по каналу l
end
end
Алгоритм 6.12 Алгоритм обхода для гиперкубов.
Теорема 6.28 Алгоритм для гиперкуба (Алгоритм 6.12) является алгоритмом x-обхода для гиперкуба.
Доказательство. Из алгоритма видно, что решение принимается после 2n пересылок маркера. Пусть p0 - инициатор, а pk - процесс, который получает маркер <num,k>. Для любого k < 2n, обозначения pk и pk+1 отличаются на 1 бит, индекс которого обозначим как l(k), удовлетворяющий следующему условию:
Т.к. для любого i < n существует равное количество k Î {0, ..., 2n} с l(k) = i, то p0 = p2n и решение принимается в инициаторе. Аналогично доказательству Теоремы 6.27, можно показать, что из pa = pb следует, что 2n|(b-a), откуда следует, что все p0, ..., p2n-1 различны.
Из всего этого следует, что, когда происходит завершение, все процессы пройдены, и после x переходов маркера будет посещен x+1 процесс.
Алгоритм обхода для произвольных связных сетей был дан Тарри в 1895 [Tarry; T1895]. Алгоритм сформулирован в следующих двух правилах; см. Алгоритм 6.13.
R1. Процесс никогда не передает маркер дважды по одному и тому же каналу.
R2. Не-инициатор передает маркер своему родителю (соседу, от которого он впервые получил маркер), только если невозможна передача по другим каналам, в соответствии с правилом R1.
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 выбор 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.13 Алгоритм обхода Тарри.
Теорема 6.29 Алгоритм Тарри (Алгоритм 6.13) является алгоритмом обхода.
Доказательство. Т.к. маркер передается не более одного раза в обоих направлениях через каждый канал, всего он передается не более 2|E| раз до завершения алгоритма. Т.к. каждый процесс передает маркер через каждый канал не более одного раза, то каждый процесс получает маркер через каждый канал не более одного раза. Каждый раз, когда маркер захватывается не-инициатором p, получается, что процесс p получил маркер на один раз больше, чем послал его. Отсюда следует, что количество каналов, инцидентных p, превышает количество каналов, использованных p, по крайней мере, на 1. Таким образом, p не принимает решение, а передает маркер дальше. Следовательно, решение принимается в инициаторе.
Далее, за 3 шага будет доказано, что когда алгоритм завершается, каждый процесс передал маркер.
(1) Все каналы, инцидентные инициатору, были пройдены один раз в обоих направлениях. Инициатором маркер был послан по всем каналам, иначе алгоритм не завершился бы. Инициатор получил маркер ровно столько же раз, сколько отправил его; т.к. инициатор получал маркер каждый раз через другой канал, то маркер пересылался через каждый канал по одному разу.
(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.
Страницы: 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
