Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 58
Текст из файла (страница 58)
В каждом вычислении есть единственный инициатор, который запускаеталгоритм, отправляя одно-единственное сообщение.2. Всякий процесс после получения сообщения либо отправляет ровно односообщение, либо принимает решение.Как следует из первых двух свойств, в каждом конечном вычислении в точности один процесс принимает решение. Говорят, что алгоритм завершает работув том единственном процессе, который принимает решение.3. Алгоритм завершает работу в инициаторе, и к тому моменту, когда этопроисходит, каждому процессу хотя бы один раз удалось отправить сообщение.В каждой достижимой конфигурации алгоритма обхода есть либо в точности одно сообщение, находящееся на этапе пересылки, либо в точности одинпроцесс, который только что принял сообщение и еще не успел отправить ответное сообщение.
С более абстрактной точки зрения все вместе взятые сообщенияв вычислении можно рассматривать как единственный объект (маркер), который переходит от одного процесса к другому и «посещает», таким образом, всепроцессы. В параграфе 7.5.4 алгоритмы обхода применяются для построения алгоритмов голосования, а для такого построения важно знать не только общеечисло переходов маркера по ходу одной волны, но и сколько переходов необходимо сделать маркеру, чтобы посетить первые x процессов.Определение 6.25.
Алгоритм называется алгоритмом f-обхода (для некоторого класса сетей), если выполнены следующие условия:1) он является алгоритмом обхода (для указанного класса);2) в каждом вычислении после совершения f(x) переходов маркер побывалне менее чем у min(N, x + 1) процессов.var recp: integer init 0;(* только для инициатора*)Для инициатора:(* Записать Neighp = {q1 , q2 , . . . , qN−1 } *)begin while recp < #Neighp dobegin send tok to qrecp +1 ;receive tok; recp := recp + 1end;decideendДля неинициатора:begin receive tok from q ; send tok to q endАлгоритм 6.9. Алгоритм последовательного опроса216Гл. 6.Кольцевой алгоритм (алгоритм 6.1) является алгоритмом обхода, и, посколькупосле x переходов маркер побывал у x + 1 процессов и посетил все процессы поокончании N-го перехода, этот алгоритм является также алгоритмом x-обходадля кольцевых сетей.6.3.1.
Обход кликВсякую клику можно обойти, воспользовавшись последовательным опросом; этот алгоритм очень похож на алгоритм 6.5, однако соседи инициатора опрашиваются здесь поочередно, и как только поступает отклик от одного соседа,проводится опрос следующего (см. алгоритм 6.9).Теорема 6.26. Алгоритм последовательного опроса (алгоритм 6.9) —это алгоритм 2x-обхода для клик.Д о к а з а т е л ь с т в о. Легко видеть, что если алгоритм завершается в инициаторе, то каждому процессу удалось прислать отклик. Запросом к процессу q xслужит (2x − 1)-е сообщение, а откликом на него является 2x-е сообщение.
Следовательно, если произошел обмен 2x сообщениями, то посетить удалось x + 1процессов p, q1 , . . . , qx .6.3.2. Обход торовТорический граф граф размера n × n — это граф G = (V, E), у которогои6.3. Алгоритмы обходаВолновые алгоритмы и алгоритмы обходаV = Zn × Zn = { (i, j) : 0 6 i, j < n}E = { (i, j) (i0 , j0) : (i = i0 ∧ j = j0 ± 1) ∨ (i = i0 ± 1 ∧ j = j0) }(см. § Б.2.4). Сложение и вычитание здесь проводится по модулю n. Предполагается, что в торе имеется восприятие направления (см.
§ Б.4.3), т. е. в вершине(i, j) канал, соединяющий эту вершину с (i, j + 1), помечен Up, канал, ведущийв вершину (i, j − 1), помечен Down, канал, ведущий в вершину (i + 1, j), помеченRight, а канал, ведущий в вершину (i − 1, j), помечен Left. Пары координат (i, j)служат удобным средством задания топологии сети и ориентации, однако мы будем считать, что процессы не располагают сведениями об этих координатах; ихпредставление о топологии ограничено метками каналов.Тор является гамильтоновым графом, т. е. в торе произвольного размера существует гамильтонов цикл, и маркер перемещается по этому циклу, руководствуясьалгоритмом 6.10. После k-го перехода маркер отправляется вверх, если n|k (nявляется делителем k); в противном случае он отправляется направо.Теорема 6.27. Алгоритм тора (алгоритм 6.10) является алгоритмомx-обхода для тора.Д о к а з а т е л ь с т в о.
Как видно из описания алгоритма, решение принимается, как только маркер был передан n2 раз. Если маркер переместился от217Для инициатора, выполнить один раз:send hnum, 1i to UpДля каждого процесса после приема маркера hnum, ki:begin if k = n2 then decideelse if n|k then send hnum, k + 1i to Upelse send hnum, k + 1i to RightendАлгоритм 6.10.
Алгоритм обхода для торапроцесса p к процессу q, совершив U переходов Up и R переходов Right, тоp = q тогда и только тогда, когда (n|U ∧ n|R). Обозначим процесс-инициаторсимволом p0 , а процесс, получивший маркер hnum, ki, обозначим символом p k .Из общего числа n2 перемещений маркера n ходов были сделаны вверх,а остальные n2 − n ходов были сделаны направо. Поскольку оба числа n и n 2 − nделятся на n, получаем, что pn2 = p0 , и это означает, что алгоритм завершаетсяв инициаторе.Далее будет показано, что все процессы, начиная от p 0 и оканчивая pn2 −1 , попарно различны. А так как у нас всего n2 процессов, отсюда следует, что посетитьудалось каждый процесс.
Допустим, pa = pb для некоторых a, b, 0 6 a < b < n2 .На участке от pa до pb маркер совершил некоторое количество переходов Upи некоторое количество переходов Right, и, поскольку p a = pb , оба числа делятся на n. Обратившись к описанию алгоритма, можно заметить, что это влечет засобой два соотношения#{k : a 6 k < b ∧ n|k} кратно n и #{k : a 6 k < b ∧ n 6 |k} кратно n.Суммарный размер этих множеств равен b − a, откуда следует, что n| (b − a).Представим это отношение в виде (b − a) = ln. Тогда множество {k : a 6 k < b}содержит l чисел, делящихся на n.
Отсюда следует, что n|l, и поэтому n 2 | (b − a),что является противоречием. Так как все процессы, начиная с p 0 и оканчиваяpn2 −1 , попарно различны, маркеру после x переходов удается посетить x + 1процессов.6.3.3. Обход гиперкубовГраф G = (V, E), в которомV = { (b0 , . . . , bn−1) : bi = 0, 1}иE = { (b0 , . . . , bn−1), (c0 , . . . , cn−1) : наборы b и c отличаются в одном бите}называется n-мерным гиперкубом (см.
§ Б.2.5). Предполагается, что в гиперкубе имеется восприятие направления (см. § Б.4.3), т. е. канал между вершинами218Гл. 6.6.3. Алгоритмы обходаВолновые алгоритмы и алгоритмы обходаb и c, отличающимися в i-м бите, помечен «i» в обеих вершинах. Предполагается также, что процессы не располагают сведениями о пометках вершин; ихпредставление о топологии ограничено знанием меток каналов.Как и в случае тора, гиперкуб является гамильтоновым графом, и гамильтонов цикл можно обойти, воспользовавшись алгоритмом 6.11. Доказательствокорректности этого алгоритма почти такое же, как для алгоритма 6.10.R2. Неинициатор передает маркер своей родительской вершине (соседу, откоторого он впервые получил маркер) только в том случае, когда его невозможнопередать по другим каналам согласно правилу R1.var usedp [q] : boolfatherpДля инициатора выполнить один раз:send hnum, 1i по каналу n − 1 .Для каждого процесса после приема маркера hnum, ki:begin if k = 2n then decideelse begin let l — наибольшее такое число, что 2l |k ;send hnum, k + 1i по каналу lendendАлгоритм 6.11.
Алгоритм обхода для гиперкубаТеорема 6.28. Алгоритм гиперкуба (алгоритм 6.11) является алгоритмом x-обхода для гиперкуба.Д о к а з а т е л ь с т в о. Как видно из описания алгоритма, решение принимается после 2n переходов маркера. Обозначим символом p0 инициатор, и пустьpk будет обозначать процесс, к которому поступил маркер hnum, ki. Для всякого k < 2n наборы, обозначающие вершины pk и pk+1 , отличаются в одном бите,индекс которого обозначим l(k). Этот индекс удовлетворяет соотношению(n − 1,если k = 0,l(k) =наибольшее такое l, что 2l |k, если k > 0.Так как для каждого i < n существует четное число таких индексов k∈{0, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
