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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 104)

Этот маркер поглощается всяким другим процессом с более стар­шим отличительным признаком, который также участвует в этом туре; маркертакже прерывает активность всех процессов, пребывающих на первом этапе ра­боты алгоритма. На втором этапе работы алгоритма гарантируется, что толькопроцесс с наибольшим отличительным признаком, сумевший пройти loga v/V-йтур, получит свой маркер обратно; этот процесс и избирается лидером.11.3. Вычисления в гиперкубах393Теорема 11.17. Описанный алгоритм позволяет избрать лидера с ис­пользованием O ( N ) обменов сообщениями на хордовом кольце с одной хор­дой (имеющей размах x/N).Д о к а з а т е л ь с т в о .

Коль скоро на первом этапе работы алгоритма невсе процессы оказываются убитыми, хоть один процесс перейдет ко второму эта­пу работы алгоритма. На втором этапе гарантируется избрание лидером в точ­ности одного процесса, и этим обосновывается корректность построенного алго­ритма.Согласно следствию 11.16 на первом этапе совершается 0(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. Следовательно, такие алгоритмы при вы­полнении на гиперкубе будут использовать по меньшей мере Cl(N log N) обменовсообщениями.С другой стороны, широковещательную рассылку можно осуществить припомощи потока или алгоритма эха (алгоритм 6.4), а выборы можно провести,используя алгоритм Галладжера и др. алгоритм 7.10/7.11/7.12). Таким образом,обе задачи можно решить с использованием 0(N log N) обменов сообщениями.Теорема 11.18. И з б р а н и е л и д е р а и ш и р о к о в е щ а т е л ь н а я р а с с ы л к а с о ­о б щ ен ий в ги п е р к у б а х без о свед ом лен ност и о т о п о ло ги и сет и т р ебует0 (iVlogiV) о б м е н о в с о о б щ е н и я м и .11.3.2. Алгоритм посредничестваВ алгоритме посреднического избрания лидеров, применяющемся для гипер­кубов с восприятием направления, используется рекурсивная структура<b>Текст обрезан, так как является слишком большим</b>.

Характеристики

Список файлов книги