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

При наличии восприятия направления в клике сложность задачи о выборах уменьшается с величины Θ (N log N) до величиныΘ (N).В случае хордового кольца общего вида Аттья ввел функцию стоимостисообщения F: это такая наименьшая монотонная и выпуклая функция, что выполнение операции Send(m, g) требует использования не более F (g) обменов сообщениями. (Функцию F можно представлять как стоимость отправления сообщения процессу g, удаленному на заданное число переходов по кольцу.) В худшемслучае в i-м туре могут принять участие N / (2i−1) активных процессов, отстоящихi−1Nпереходов, и на нем придется использовать i−1 × 4 × F (2друг от друга на 22передач сообщений.i−1)nP−1 F (2i)Лемма 11.9.

В худшем случае в алгоритме 11.4 используется 4N·ii=0 2передач сообщений.Лемма устанавливает, как общая сложность проведения выборов зависит отстоимости отправления сообщений на кольце. В особых случаях сложность проведения выборов на кольце (где F (g) = g) и клике (где F (g) = 1) будет составлятьвеличину O(N log N) и O(N), соответственно.

Аттья и др. показали, что логарифмического числа хорд достаточно, чтобы ограничить эту сумму константой,например для хордового кольца CN (2, 3, 4, . . . , lg N). Мы воздержимся здесь отвоспроизведения выкладок.procedure Send(m, g):begin ifg = 0then deliver message m to waiting Receiveelse begin ch := the largest of gi such that ch 6 g;send hm, g − gi i through link chendendUpon receipt of hm, gi:Send(m, g)Алгоритм 11.5. Стратегия жадной маршрутизации387результат отражает общую тенденцию в изучении алгоритмов, когда исследования становятся все менее «алгоритмическими», а основное внимание уделяетсяанализу.

Действительно, коль скоро алгоритмическая сторона задачи о выборах разработана и отношения между хордами и сложностью задачи оказались«cпрятаны» в формулах леммы 11.9), наши усилия сосредотачиваются на работес формулами.Сумма геометрической прогрессии. Коль скоро геометрическая прогрессия (знаменатель которой меньше 1) имеет ограниченную сумму, мы вначале поF (2i)пробуем выяснить, сколько хорд необходимо, чтобы ограничить дробьве2iличиной вида ci , где c < 1.Рассмотрим последовательность хорд L = {2, 4, 16, 256, .

. . }, в которой охваткаждой последующей хорды выражается величиной, составляющей квадрат отаналогичного показателя предыдущей; последовательность оканчивается, когдаiразмах очередной хорды превосходит N. Размах хорд выражается формулой 2 2 ,а их число равно log log N.√Лемма 11.10. F (d) 6 2 · d.Д о к а з а т е л ь с т в о.

Проведем индукцию по d, используя жадную маршрутизацию, в которой построение пути, составляющего сумму d, начинается снаибольшей хорды l,√подходящей для d, и далее пойдем по пути длины d − l.Вначале F (1) = 1 6 2 1.Предположим теперь, что d > 0 и наше соотношение справедливо для всякоготак, что самая длинная хорда, подходящая для dd0 < d. Выбор хорд проводится√имеет такую длину l, что d < l 6 d. В результате мы получаем неравенстваq√√√F (d) 6 1 + F (d − l) 6 1 + 2 d − l < 1 + 2 d − d < 2 d.Таким образом, дробьF (2i)1ограничена величиной 2· √2i2i, ряд, представлен-ный в лемме 11.9 ограничивается суммой, и эта сумма ограничена сверху.

Мы показали, что выборы с линейной сложностью возможны при наличии O(log log N)хорд. Оказывается, что Ω (log log N) также и необходимо (если применяется жадная маршрутизация), чтобы ограничиться суммированием геометрической прогрессии!Лемма 11.11. Если существует такая константа c < 1, что при исF (2i)11.2.3. Минимизация числа хордРезультат Аттьи устанавливает, что сложность проведения выборов на хордовых кольцах линейна; теперь сосредоточим внимание на задаче минимизациичисла хорд, необходимого для достижения такой сложности. В этом параграфемы установим асимптотику числа хорд, которое необходимо алгоритму Аттьи,используя метод «восстановления графа по формуле».

Представленный здесьпользовании жадной маршрутизации выполняется неравенство i2то число хорд составляет величину Ω (log log N).< ci ,Д о к а з а т е л ь с т в о. Для каждого i < log N имеет место неравенствоF (2i) < ci · 2i , и отсюда следует, что задействованы хорды, размах которых неменьше (1/c) i . В соответствии со стратегией жадной маршрутизации длина такойхорды не превышает 2i . Следовательно, для каждого i есть хорда, размах которойлежит в отрезке [(1/c) i . . . 2i ] .

Заметим, что при i0 = i · log 1/c отрезки для i и i0388Гл. 11. Восприятие направления и ориентация11.2. Выборы на кольцах и хордовых кольцахне пересекаются. Значит, для log log N различных значений i r = (log 1/c) r (гдеr < log log N) мы получаем семейство непересекающихся отрезков [(1 /c) ir . . . 2ir ] ,в каждом из которых укладывается размах некоторой хорды.Применение других стратегий маршрутизации позволит, пожалуй, улучшитьлишь постоянный множитель; доказательство этого тезиса остается открытымвопросом.

Построение F по заданному L связано с задачей о размене монеты, в которой требуется выплатить оговоренную сумму, используя лишь монетыопределенного достоинства. Общая стратегия маршрутизации предусматриваетиспользование результата решения задачи о размене монеты.Более медленно убывающие суммы. Мы убедились, что геометрическаяпрогрессия в соотношении из леммы 11.9 приводит к линейной сложности, нопри этом требуется проведение Θ (log log N) хорд. Поэтому мы выберем последовательность, которая убывает еще медленнее, но при этом обладает ограниченнойPсуммой, а именно, квадратично-гармоническую последовательность (1/i2).Рассмотримсемейство хорд L = {36, 64, 256, 65 536, .

. . }, в котором g i+1 =√= 2 gi ; 36 является наименьшим числом, для которого эта формула дает большуюстепень 2. Так как gi = log2 (gi+1), для каждого d существует хорда, размахкоторой попадает в промежуток между log2 d и d.Лемма 11.12. В L содержится менее 2 log∗ N хорд.√√√√giД о к а з а т е л ь с т в о. Так как gi+2 = 2 2 i = 2 ( 2 ) > 2gi , последовательность величин g0 , g2 , g4 , g6 , . . . возрастает быстрее, чем последовательность2g222, 22 , 22 , 22 , . . ., и ее члены будут превышать N спустя log∗ N шагов.Для маршрутизации сообщений на короткие дистанции (d < 36) нужны короткие хорды, но их будет всего лишь некоторое фиксированное число.Лемма 11.13. Справедливо неравенство F (d) 6 2 ·dlog2 d.Д о к а з а т е л ь с т в о.

Для больших значений d алгоритм жадной маршрутизации сначала выберет хорду l, размах которой превышает log 2 d. В результатебудет получены следующие соотношения:F (d) = 1 + F (d − l) 6 1 + 2 ·d−l2log (d − l)<1+2·d − log2 d22log (d − log d)<2·dlog2 d.Проведенные вычисления показывают, что для того, чтобы провести выборыс линейной сложностью, достаточно Θ (log∗ N) хорд. Теперь перейдем к соответствующей нижней оценке числа хорд. Доказательство основывается на вычислении сумм ряда, элементы которого убываютPеще медленнее, но при этом самисуммы не ограничены: это гармонический ряд (1/i).

Известно, что первые log nчленов этого ряда дают в сумме величину, составляющую Θ (log log N), однакодля того, чтобы ее достичь, требуется Ω (log∗ N) хорд!Лемма 11.14. Если применяется жадная маршрутизация и верно неравенствоF (2i)< 1/i, то имеется, по меньшей мере, log∗ N хорд.2i389Д о к а з а т е л ь с т в о.

Доказательство проводится так же, как была обоснована предыдущая нижняя оценка: для каждого i должна найтись хорда, размахкоторой укладывается в отрезок между i и 2i .Подведем итоги:1) O(log∗ N) хорд достаточно для сходимости квадратично-гармоническогоряда (лемма 11.13);2) Ω (log∗ N) хорд требуется для расходимости гармонического ряда (лемма 11.14).Чтобы получить линейную сложность, суммы из леммы 11.9 должны бытьограничены, и, следовательно, должны убывать быстрее, нежели суммы гармонического ряда; для этого требуется, по меньшей мере, Ω (log ∗ N) хорд.

Отсюдаследует, что Θ (log∗ N) хорд необходимо и достаточно для того чтобы алгоритмАттьи имел линейную сложность.11.2.4. Однохордовый линейный алгоритмВ этом параграфе будет представлен алгоритм избрания лидера на хордовомкольце, имеющий линейную сложность и требующий всего лишь одной хорды.Мы уже убедились в том, что алгоритм Аттьи этого сделать не может: в немиспользуется лишь способность сжимать пути, а структура сети никакой роли неиграет.Рассмотрим теперь хордовое кольцо с одной-единственной хордой√ размаха t,и при этом будем полагать, что величина t приближенно равна N.√ Топологияхордового кольца с единственной хордой, размах которой близок к N, напоминает тор, и наш алгоритм будет представлять собой адаптацию алгоритма Петерсона (см. [160]) для торов.В начале каждого тура всякий активный процесс пытается отыскать, или увидеть, другой процесс, который считается активным в том же самом туре; процессвидит самое большее еще один процесс, но его могут видеть многие процессы.Есть два способа продвижения какого-либо активного процесса в следующийтур.Первый из них весьма похож на продвижение по принципу «локального максимума» из алгоритма Франклина: если процесс замечает другой процесс с младшим именем и его также замечает процесс с младшим именем, то наш процесспереходит в следующий тур.