Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 68
Текст из файла (страница 68)
Чтобы вывести отсюда нижнюю оценку сложности такогоалгоритма, определим две меры множества E. Будем говорить, что набор t появляется как последовательный набор отличительных признаков в s-кольце, еслиt — это префикс какого-нибудь набора r ∈ CS(s). В качестве меры M(s, E) выбирается количество наборов множества E, которые появляются последовательнов s-кольце, а в качестве Mk (s, E) — количество всех таких наборов длины k, т. е.M(s, E) =|{t ∈ E : t является префиксом некоторого набора r ∈ CS(s) }|,Mk (s, E) =|{t ∈ E : t является префиксом некоторого набора r ∈ CS(s) и len(t) = k}|.Далее мы будем рассматривать произвольный алгоритм A вычисления самогомладшего отличительного признака, а запись E A будем использовать для обозначения множества таких наборов s, что по ходу выполнения алгоритма A наs-кольце отправляется некоторое s-сообщение.Лемма 7.10.
Если оба набора t и u содержат набор s в качестве подстроки и по ходу работы алгоритма A на t-кольце отправляется некоторое s-сообщение, то какое-нибудь s-сообщение будет также отправленопо ходу работы алгоритма A на u-кольце.Д о к а з а т е л ь с т в о. Отправление s-сообщения процессом sk , где s == (s1 , . . . , sk), связано причинно-следственной зависимостью только с процессами si , 1 6 i 6 k. Их начальное состояние в u-кольце будет тем же самым, чтои в t-кольце (здесь уместно напомнить, что размер кольца неизвестен), и, следовательно, все события, предшествующие отправлению рассматриваемого сообщения, также осуществятся и в u-кольце.Лемма 7.11.
Множество EA является исчерпывающим множеством.Д о к а з а т е л ь с т в о. Чтобы убедиться в том, что EA является префикснозамкнутым, заметим, что если A отправляет какое-нибудь s-сообщение по ходуработы на s-кольце, то это означает, что для всякого префикса t набора s алгоритм A сначала должен был отправить t-сообщение на том же самом s-кольце.1) Решающегозадачу о выборах. — Прим.
перев.256Гл. 7. Алгоритмы избрания лидераПо лемме 7.10 алгоритм A, таким образом, отправляет t-сообщения на t-кольце,и, значит, t ∈ EA .Чтобы убедиться в том, что EA циклически покрывает множество D, рассмотрим некоторое вычисление алгоритма A на s-кольце. По крайней мере одинпроцесс должен принять решение относительно самого младшего отличительного признака, и отсюда следует (рассуждения здесь будут подобны тем, которыепроводились при доказательстве теоремы 6.11), что указанный процесс получилсообщение, длина трассы которого равна len(s). Эта трасса является циклическим сдвигом набора s и содержится в EA .Лемма 7.12.
По ходу работы алгоритма A на s-кольце отправляетсяне менее M(s, EA) сообщений.Д о к а з а т е л ь с т в о. Рассмотрим произвольный префикс t, t ∈ E A , циклического сдвига r набора s. По определению EA некоторое t-сообщение отправляется по ходу работы алгоритма A на t-кольце. Значит, оно так же отправляетсяи по ходу работы алгоритма на r-кольце, которое совпадает с s-кольцом. Следовательно, для каждого элемента t из множества{t ∈ EA : t является префиксом некоторого набора r ∈ CS(s) }7.2. Кольцевые сети257Д о к а з а т е л ь с т в о. Проводя усреднение по всем начальным конфигурациям, помеченным множеством I, мы получаем следующие соотношения:1 XaveA (I) >M(s, EA) =N!1=N!=s∈Per(I)NX XMk (s, EA) =s∈Per(I) k=1N1 X XMk (s, EA).N!k=1 s∈Per(I)Зафиксируем k и заметим, что для каждого набора s ∈ Per(I) имеется N префиксовдлины k, которыми начинаются циклические сдвиги набора s. Так как множествоPer(I) содержит N! перестановок, общее число таких префиксов будет достигатьвеличины N · N!.
Эти префиксы можно разбить на N · N! /k групп, в каждой изкоторых содержится k циклических сдвигов одного и того же набора. ПосколькуEA циклически покрывает D, множество EA пересекается с каждой такой группой,и поэтому справедливо неравенствоXN · N!Mk (s, EA) >.ks∈Per(I)Отсюда и следует оценкахотя бы одно t-сообщение отправляется по ходу вычисления на s-кольце, а этосвидетельствует о том, что количество обменов сообщениями в таком вычислениибудет не меньше, чем M(s, EA).Для всякого множества I отличительных признаков процессов обозначим выражением Per(I) множество всех перестановок множества I.
Введем запись ave A (I)для обозначения среднего числа обменов сообщениями, используемых алгоритмом A на всех кольцах, помеченных отличительными признаками из множестваI, а запись worA (I) для обозначения числа обменов сообщениями, используемыхв наихудшем случае. Из предшествующей леммы следует, что если множество Iсостоит из N элементов, то выполняются следующие неравенства:1 PM(s, EA);1) aveA (I) >aveA (I) >N1 X N · N!= N · HN .N!kk=1Этот результат свидетельствует о том, что алгоритм Ченя —Робертса является оптимальным, если речь идет о сложности в среднем. Оценка сложностив наихудшем случае будет, по крайней мере, не меньше, чем оценка сложностив среднем, а это означает, что самая точная оценка сложности в наихудшем случае расположена между величиной N · HN ≈ 0.69N log N и величиной 1.356N log N.Доказательство, приведенное в этом параграфе, существенно опирается надопущения о том, что кольцо является однонаправленным, и что размер кольца12) worA (I) > maxs∈Per(I) M(s, EA).Нижнюю оценку теперь можно установить путем анализа произвольного исчерпывающего множества.неизвестен.
Нижняя оценка N · HN была получена Бодлаендером в работе [31]2для сложности в среднем алгоритмов решения задачи о выборах на двунаправленных кольцах при условии, что размер кольца неизвестен. Чтобы устранитьнедетерминизм в случае двунаправленных колец, пришлось рассматривать вычисления, в которых каждый процесс начинает работу в одно и то же время, акаждое сообщение имеет одну и ту же задержку при передаче. Для случая, когдаТеорема 7.13. Сложность в среднем всякого однонаправленного алгоритма отыскания самого младшего отличительного признака будет неменьше чем N · HN .размер кольце известен, Бодлаендер [32] получил нижнюю оценку N log N на21однонаправленных кольцах и− NHN на двунаправленных кольцах (в обоих4случаях речь идет о сложности в среднем).N! s∈Per(I)1258Гл. 7.
Алгоритмы избрания лидераПодводя итоги, заметим, что почти все сделанные нами допущения не влияютна сложность выборов на кольце. Независимо от того, известен или неизвестенразмер кольца, является ли кольцо однонаправленным или двунаправленным,рассматривается ли средний или наихудший случай, всякий раз сложность составляет величину Θ (N log N). Здесь существенно то, что кольцо асинхронно;как будет показано в гл.
12, для сетей, имеющих доступ к глобальному времени,сложность по числу обменов сообщениями будет меньше.Так как лидера можно избрать по ходу одного-единственного вычисления децентрализованного волнового алгоритма, из нижней оценки сложности выборовследует и нижняя оценка сложности для волновых алгоритмов.Следствие 7.14. По ходу работы всякого децентрализованного алгоритма на кольцевых сетях происходит обмен, по меньшей мере, Ω (N log N)сообщениями, как в среднем, так и в наихудшем случае.7.3. Произвольные сетиТеперь перейдем к изучению задачи о выборах для сетей произвольной, заранее неизвестной топологии при условии отсутствия сведений о соседях. Далеемы установим нижнюю оценку Ω (N log N + |E|) числа обменов сообщениями.
Приобосновании ее мы будем сочетать идеи доказательства теоремы 6.6 и результаты предыдущего параграфа. В § 7.3.1 будет приведен простой алгоритм, имеющиймалую сложность по времени, но большую сложность по числу обменов сообщениями в наихудшем случае. В § 7.3.2 будет представлен алгоритм, являющийсяоптимальным по сложности в наихудшем случае.Теорема 7.15. Всякий алгоритм избрания лидера на основе сравнениядля произвольных сетей имеет сложность (и в среднем, и в наихудшемслучае), не меньшую чем Ω (|E| + N log N).Д о к а з а т е л ь с т в о.
Слагаемое Ω (N log N) служит нижней оценкой, потому что произвольные сети включают в себя и кольца, для которых соблюдаетсянижняя оценка Ω (N log N). Чтобы убедиться в том, что |E| обменов сообщениямислужит нижней оценкой даже для самого лучшего из всех вычислений, допустим, что некоторый алгоритм избрания A допускает вычисление C на сети G,в ходе которого осуществляется обмен менее чем |E| сообщениями (см. рис. 7.8).Построим сеть G0 , соединив две копии сети G ребром, связывающим два узла,которые вставлены в каждой копии сети G посреди ребра, не задействованногов вычислении C. Отличительные признаки в обеих частях построенной сети сохраняют тот же относительный порядок, что и в сети G. Вычисление C можнопромоделировать совместно в обеих частях сети G 0 , и, таким образом, мы получимвычисление, в результате которого лидерами будут избраны два процесса.Следствие 7.16. Всякий децентрализованный волновой алгоритм дляпроизвольных сетей без предварительной осведомленности о соседях имеет сложность по числу обменов сообщениями, не меньшую чем Ω (|E|+N log N).7.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
