Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 102
Текст из файла (страница 102)
И это вновь благоприятно для нас, поскольку Корач и др. в работе [119] установили нижнюю оценкуfl(N log N) для задачи о выборах на кликах без восприятия направления.386Гл. 11. Восприятие направления и ориентацияСледствие 11.8. При наличии восприятия направления в клике сложность задачи о выборах уменьшается с величины O(AlogA) до величины©(до.В случае хордового кольца общего вида Аттья ввел функцию стоимостисообщения F: это такая наименьшая монотонная и выпуклая функция, что выполнение операции Send(m, g ) требует использования не более F(g) обменов сообщениями. (Функцию F можно представлять как стоимость отправления сообщения процессу g, удаленному на заданное число переходов по кольцу.) В худшемслучае в /- м туре могут принять участие N/(2l~l) активных процессов, отстоящихдруг от друга напереходов, и на нем придется использоватьх 4 х F(2‘~ 1)21 1передач сообщений.п—1Лемма 11.9.
В худшем случае в алгоритме 11.4 используется 4N- ^2передач сообщений.!~°F(У)2'Лемма устанавливает, как общая сложность проведения выборов зависит отстоимости отправления сообщений на кольце. В особых случаях сложность проведения выборов на кольце (где F(g) g) и клике (где Fig) = 1) будет составлятьвеличину 0(A logA ) и О(А), соответственно. Аттья и др. показали, что логарифмического числа хорд достаточно, чтобы ограничить эту сумму константой,например для хордового кольца Сдг(2, 3, 4, . . . , IgA).
Мы воздержимся здесь отвоспроизведения выкладок.procedure Send(m, g)\begin ifg = 0then deliver m essage m to waiting Receiveelse begin ch := the largest of gi such that ch < g;send (tn, g —gi) through linkchendendUpon receipt of(m, g):Send(m, g)Алгоритм 11.5.Стратегия жадной маршрутизации11.2.3. Минимизация числа хордРезультат Аттьи устанавливает, что сложность проведения выборов на хордовых кольцах линейна; теперь сосредоточим внимание на задаче минимизациичисла хорд, необходимого для достижения такой сложности. В этом параграфемы установим асимптотику числа хорд, которое необходимо алгоритму Аттьи,используя метод «восстановления графа по формуле».
Представленный здесь11.2. Выборы на кольцах и хордовых кольцах387результат отражает общую тенденцию в изучении алгоритмов, когда исследования становятся все менее «алгоритмическими», а основное внимание уделяетсяанализу. Действительно, коль скоро алгоритмическая сторона задачи о выборах разработана и отношения между хордами и сложностью задачи оказались«спрятаны» в формулах леммы 11.9), наши усилия сосредотачиваются на работес формулами.Сумма геометрической прогрессии.
Коль скоро геометрическая прогрессия (знаменатель которой меньше 1 ) имеет ограниченную сумму, мы вначале поF(2 ')пробуем выяснить, сколько хорд необходимо, чтобы ограничить дробь —^ величиной вида с1, где с < 1 .Рассмотрим последовательность хорд/.
= {2, 4, 16, 256, ... }, в которой охваткаждой последующей хорды выражается величиной, составляющей квадрат отаналогичного показателя предыдущей; последовательность оканчивается, когдаразмах очередной хорды превосходит N. Размах хорд выражается формулой 22 ,а их число равно log log N.Лемма 11.10. F(d) ^ 2 • \fd.Д о к а з а т е л ь с т в о . Проведем индукцию по d, используя жадную маршрутизацию, в которой построение пути, составляющего сумму d, начинается снаибольшей хорды /, подходящей для d, и далее пойдем по пути длины d — I.Вначале К(1 ) = 1 ^ 2vT.Предположим теперь, что d > Он наше соотношение справедливо для всякогоd1 < d. Выбор хорд проводится так, что самая длинная хорда, подходящая для dимеет такую длину /, что \fd < / ^ d.
В результате мы получаем неравенстваF{d) ^ 1 + F { d - l ) ^ 1 + 2 V I ^ i < 1 + 2 \ f d W ^ < 2y/d.□F(2l) ограничена величиной 2 , ряд, представлен2‘ный в лемме 11.9 ограничивается суммой, и эта сумма ограничена сверху. Мы показали, что выборы с линейной сложностью возможны при наличии O(loglogiV)хорд. Оказывается, что П (log log IV) также и необходимо (если применяется жадная маршрутизация), чтобы ограничиться суммированием геометрической прогрессии!Таким образом, дробьЛемма 11.11.
Если существует такая константа с < 1, что при ис..F&)пользовании жадной маршрутизации выполняется неравенство —t— < с ,то число хорд составляет величину n(loglogiV).Д о к а з а т е л ь с т в о . Для каждого i < logIV имеет место неравенствоF(2l) < с1 ■2 !, и отсюда следует, что задействованы хорды, размах которых неменьше (1/с)!. В соответствии со стратегией жадной маршрутизации длина такойхорды не превышает 2'. Следовательно, для каждого i есть хорда, размах которойлежит в отрезке [(1 /с)1...
2']. Заметим, что при i' = i ■log 1/с отрезки для / и i'388Гл. 11. Восприятие направления и ориентацияне пересекаются. Значит, для log log jV различных значений ir = (log 1/с)г (гдег < log log N) мы получаем семейство непересекающихся отрезков [ ( 1 /с)1' ... 2 'г],в каждом из которых укладывается размах некоторой хорды.□Применение других стратегий маршрутизации позволит, пожалуй, улучшитьлишь постоянный множитель; доказательство этого тезиса остается открытымвопросом.
Построение F по заданному L связано с задачей о размене монеты, в которой требуется выплатить оговоренную сумму, используя лишь монетыопределенного достоинства. Общая стратегия маршрутизации предусматриваетиспользование результата решения задачи о размене монеты.Более медленно убывающие суммы. Мы убедились, что геометрическаяпрогрессия в соотношении из леммы 11.9 приводит к линейной сложности, нопри этом требуется проведение 0(loglogiV) хорд.
Поэтому мы выберем последовательность, которая убывает еще медленнее, но при этом обладает ограниченнойсуммой, а именно, квадратично-гармоническую последовательность J ] ( l / / 2).Рассмотрим семейство хорд L = {36, 64, 256, 65 536, ... }, в котором g,+i == 2 VS; 36 является наименьшим числом, для которого эта формула дает большуюстепень 2. Так как gt = log2 (gri+i), для каждого d существует хорда, размахкоторой попадает в промежуток между log2 d и d.Лемма 11.12. В L содержится менее 2 log* N хорд.Д о к а з а т е л ь с т в о .
Так как g , + 2 == 2(^ 2'/W) > 2&, последовательность величин go, g 2 , g 4 , g 6 , • • • возрастает быстрее, чем последовательность22^2 , 2 2, 2, 2 2 , ..., и ее члены будут превышать N спустя log* N шагов.□Для маршрутизации сообщений на короткие дистанции (d < 36) нужны короткие хорды, но их будет всего лишь некоторое фиксированное число.Лемма 11.13. Справедливо неравенство F(d) ^ 2 • — =—.log2 ofД о к а з а т е л ь с т в о . Для больших значений d алгоритм жадной маршрутизации сначала выберет хорду /, размах которой превышает log2 d. В результатебудет получены следующие соотношения:d- l■log2 d< 1+ 2 <2□log2 (c? ■ log2 d)log (d - 1)log2 d 'Проведенные вычисления показывают, что для того, чтобы провести выборыс линейной сложностью, достаточно 0(log* N) хорд.
Теперь перейдем к соответствующей нижней оценке числа хорд. Доказательство основывается на вычислении сумм ряда, элементы которого убывают еще медленнее, но при этом самисуммы не ограничены: это гармонический ряд XXV0- Известно, что первые log лчленов этого ряда дают в сумме величину, составляющую ©(logloglV), однакодля того, чтобы ее достичь, требуется H(log* N) хорд!F(d) = \ + F ( d - l ) ^ \ + 2'Лемма 11.14. Если применяется жадная маршрутизация и верно неравенство F(2‘) < 1/г, то имеется, по меньшей мере, log* N хорд.2'11.2. Выборы на кольцах и хордовых кольцах389Д о к а з а т е л ь с т в о . Доказательство проводится так же, как была обоснована предыдущая нижняя оценка: для каждого i должна найтись хорда, размахкоторой укладывается в отрезок между i и 2 ‘.□Подведем итоги:1) 0(log* N) хорд достаточно для сходимости квадратично-гармоническогоряда (лемма 11.13);2) H(log* N) хорд требуется для расходимости гармонического ряда (лемма 11.14).Чтобы получить линейную сложность, суммы из леммы 11.9 должны бытьограничены, и, следовательно, должны убывать быстрее, нежели суммы гармонического ряда; для этого требуется, по меньшей мере, fi(log* N) хорд.
Отсюдаследует, что 0(log* N) хорд необходимо и достаточно для того чтобы алгоритмАттьи имел линейную сложность.11.2.4. Однохордовый линейный алгоритмВ этом параграфе будет представлен алгоритм избрания лидера на хордовомкольце, имеющий линейную сложность и требующий всего лишь одной хорды.Мы уже убедились в том, что алгоритм Аттьи этого сделать не может: в немиспользуется лишь способность сжимать пути, а структура сети никакой роли неиграет.Рассмотрим теперь хордовое кольцо с одной-единственной хордой размаха t,и при этом будем полагать, что величина t приближенно равна \/А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
