Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf), страница 104

Коль скоро на первом этапе работы алгоритма невсе процессы оказываются убитыми, хоть один процесс перейдет ко второму этапу работы алгоритма. На втором этапе гарантируется избрание лидером в точности одного процесса, и этим обосновывается корректность построенного алгоритма.Согласно следствию 11.16 на первом этапе совершается O(N) обменов сообщениями, а на втором этапе происходит только O(N) обменов сообщениями,поскольку на этом этапе число процессов, отправивших маркер по кольцу, ограничено константой.11.3. Вычисления в гиперкубахВ этом параграфе мы исследуем вопрос о том, позволяет ли восприятие направления уменьшить сложность широковещательного распространения сообщений и проведения выборов в гиперкубах.

Долгое время предполагалось, что ответна этот вопрос должен быть утвердительным, потому что известные алгоритмы,в которых используется восприятие направления, превосходили по качеству наилучшие известные алгоритмы, работающие в неразмеченных гиперкубах. Тем неменее, ввиду отсутствия соответствующих нижних оценок для случая неразмеченных гиперкубов строгого обоснования получить не удавалось.В последние годы были предложены невероятно эффективные алгоритмы длянеразмеченных гиперкубов, ликвидировавшие разрыв в известных оценках сложности между случаями размеченных и неразмеченных гиперкубов. В § 11.3.1 рассматривается случай, когда в сети отсутствует восприятие направления и нетникакой осведомленности о топологии сети; т.

е. мы рассматриваем алгоритмы,которые работают корректно в произвольной сети, и изучаем их сложность приработе в гиперкубе. В § 11.3.2 мы обратимся к тому случаю, когда наличествуеткак осведомленность о топологии, так и восприятие направления, и продемонстрируем, насколько элегантными, простыми и эффективными могут быть полученные алгоритмы.Трудной частью исследований является случай, когда есть осведомленностьо топологии сети, но нет восприятия направления: это значит, что от алгоритма требуется всего лишь правильная работа в гиперкубах, но при этом никакойразумной разметки ребер не предполагается. Было установлено, что широковещательную рассылку сообщений можно провести с использованием линейногочисла обменов сообщениями; в § 11.3.3 представлен алгоритм ориентации гиперкуба, а в § 11.3.4 введен метод трафаретов и алгоритм широковещательнойрассылки сообщений.

В § 11.3.5 обсуждаются некоторые методы, используемыев современных алгоритмах проведения выборов лидера для неразмеченных гиперкубов. Случай, когда есть восприятие направления, но нет осведомленностио топологии, нами не рассматривается.394Гл. 11. Восприятие направления и ориентация11.3.1. Базис: отсутствие осведомленности о топологии сетиПри отсутствии восприятия направления и осведомленности о топологии сети, для проведения как широковещательной рассылки, так и выборов лидератребуется, чтобы были задействованы все дуги сети для передачи хотя бы одногосообщения.

Действительно, обязательное условие правильной работы алгоритмана всяком графе позволяет воспользоваться методом «вставки вершины», как этобыло сделано в теоремах 6.6 и 7.15. Следовательно, такие алгоритмы при выполнении на гиперкубе будут использовать по меньшей мере Ω (N log N) обменовсообщениями.С другой стороны, широковещательную рассылку можно осуществить припомощи потока или алгоритма эха (алгоритм 6.4), а выборы можно провести,используя алгоритм Галладжера и др.

алгоритм 7.10 /7.11/7.12). Таким образом,обе задачи можно решить с использованием O(N log N) обменов сообщениями.Теорема 11.18. Избрание лидера и широковещательная рассылка сообщений в гиперкубах без осведомленности о топологии сети требуетΘ (N log N) обменов сообщениями.11.3.2.

Алгоритм посредничестваВ алгоритме посреднического избрания лидеров, применяющемся для гиперкубов с восприятием направления, используется рекурсивная структура гиперкубического графа. Чтобы избрать лидера в гиперкубе размерности d + 1, этоталгоритм вначале проводит выборы в каждой грани размерности d, образованнойвсеми порождающими элементами, за исключением последнего, а затем избираетлидером одного из этих двух победителей. Во избежание путаницы между лидерствами на различных этапах работы алгоритма вершина называется d-лидером,если ей удалось одержать победу в выборах в одной из d-мерных граней.Базу для работы алгоритма создают выборы в грани размерности, и она проста; сеть состоит в точности из одной вершины, которая становится 0-лидеромнепосредственно.Турнир.

Вершина, ставшая d-лидером (для d < n), приглашается на турнирс d-лидером смежной по направлению d грани. Турнир между двумя вершинами,которые могут сообщаться друг с другом прямо, организовать просто. Каждаявершина отправляет другой вершине сообщение, в котором содержится ее имя;вершина, которой будет доставлено более старшее имя, чем ее собственное, становится нелидером, а вершина, которой будет доставлено более младшее имя,чем ее собственное, становится лидером.Турнир между двумя d-лидерами проводится точно так же, за исключениемзатруднения, касающегося того, что вершины не знают, как добраться до лидерана другой (или даже на их собственной) грани. В качестве первого шага вершина p, ставшая d-лидером, отправляет извещение о турнире htour, p, di, в которомсодержится ее имя и номер этапа d, по дуге, исходящей из нее в направленииd; это сообщение получает одна из вершин другой d-мерной грани. При этом11.3.

Вычисления в гиперкубах395на вершину, принявшую указанное сообщение, которую будем теперь называтьвходной вершиной, возлагается обязанность доставить это сообщение своемуd-лидеру.Трудность доставки рассматриваемого сообщения d-лидеру состоит в том,что входная вершина не осведомлена об относительном местоположении своегоd-лидера. Для d-лидера было бы слишком накладно оповещать о своем местоположении все вершины своего d-мерного куба, чтобы входная вершина могладоставить сообщение за d шагов. Такое оповещение обошлось бы в 2 d − 1 обменов сообщениями, и это привело бы весь алгоритм проведения выборов к общейсложности O(N log N).

Точно так же, было бы накладно обязывать входную вершину рассылать извещение о турнире широковещательно по всему d-кубу; на этотоже потребовалось бы 2d − 1 обменов сообщениями.В нашем решении используется сочетание этих двух основных стратегий:d-лидер объявляет о своем статусе всем вершинам bd /2c-мерной грани, которуюв дальнейшем будем называть строкой лидера. Входная вершина осуществляетшироковещательную рассылку извещения о турнире по грани размерности dd /2e,которая называется ее столбцом. Так как каждая строка пересекается с каждым столбцом в точности в одной точке (это будет показано далее), найдется одна вершина, которая получит оба сообщения: и оповещение от своего d-лидера,и извещение о турнире.

Эту вершину будем называть вершиной-посредником.Вершина-посредник переправит извещение о турнире далее своему d-лидеру поостовному дереву, которое проведет оповещение лидера.Определение 11.19. Пусть задан гиперкуб размерности d.Строкой называется грань в гиперкубе, которую образуют порождающие элементы начиная с 0 и оканчивая bd/2c − 1. Столбцом называется грань в гиперкубе, которую образуют порождающие элементы начиная с bd /2c и оканчиваяd − 1.Турнир между двумя лидерами проводится следующим образом.1. d-лидер p отправляет сообщение htour, p, di по каналу d;2.

d-лидер широковещательно информирует свою строку о своем статусе,используя алгоритм 11.2; вершины строки сохраняют в памяти номер канала, покоторому они получили оповещение, и в результате образуется остовное деревоэтой строки; (алгоритм широковещательной рассылки имеет простой вид, потомучто порождающие элементы не зависят друг от друга, и каждое значение n i равно1; счетчик переходов в сообщении можно подавить);3.

входная вершина (т. е. вершина, получившая извещение htour, p, di поканалу d) широковещательно информирует об этом свой столбец, используя всетот же алгоритм 11.2.4. процесс q, не являющийся d-лидером, но расположенный в строке лидера(это означает, что q уже получил сообщение hann, di) и получивший сообщениеhtour, p, di, отправляет это сообщение своей родительской вершине;5. d-лидер q после получения сообщения htour, p, di сравнивает значения pи q.

Если q > p, то процесс q становится (d + 1) -лидером; в противном случае qстановится нелидером.396Гл. 11. Восприятие направления и ориентацияКоммуникационная сложность. Условимся обозначать записью T (d) количество обменов сообщениями, совершенных на турнире между двумя d-лидерами, а записью E(n) — количество обменов сообщениями, которое используетсяпри работе алгоритма избрания лидера (на гиперкубе размерности n). Так какдля проведения выборов требуется проведение выборов в двух кубах меньшейразмерности, а также проведение турнира, мы получаем следующее рекурсивноесоотношение0,если n = 0,E(n) =2 · E(n − 1) + T (n − 1) в противном случае.Для анализа сложности по числу обменов сообщениями нам понадобится ужеизвестная формула суммы бесконечной убывающей геометрической прогрессии(со знаменателем < 1) и ее производная по :∞Xc=0c1=1−∞Xиc=0c·c−11=.(1 − ) 2Подсчитывая число обменов сообщениями на каждом шаге турнира междудвумя d-лидерами, мы обнаружим, что:шаг 1: 2 сообщения;шаг 2: 2 · (2bd/2c − 1) сообщений;шаг 3: 2 · (2dd/2e − 1) сообщений;шаг 4: at most 2 · bd/2c сообщений;В сумме мы имеем T (d) 6 2 · (2bd/2c + 2dd/2e + bd/2c − 1).Для четных значений d мы имеем bd/2c = dd/2e = d/2, а для нечетных11значений d выполняются равенства bd/2c = (d/2) − и dd/2e = (d/2) + ; на22основании этого мы получаем= 2 · (2c + 2c + c − 1) = 4 · 2c + 2c − 2,T (2c)T (2c + 1) = 2 · (2c + 2c+1 + c − 1) = 6 · 2c + 2c − 2.Введем функцию F (n) = E(n) /2n и, воспользовавшись рекурсивным соотношением для E, получим соотношение(0,если n = 0,F (n) =T (n − 1)F (n − 1) +в противном случае.n2Оно позволяет нам записать F (n) в виде конечной суммы, которую можно оценитьсверху суммой бесконечного ряда:F (n) =n−1Xd=0T (d)<2d+1∞Xd=0T (d).2d+1Теперь воспользуемся выражением для T, которое было выведено нами для четных и нечетных значений d, рассортируем слагаемые числителя на показательные,11.3.