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

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

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

. . , s/Д, если именно в та­ком порядке в кольце размера N расположены отличительные признаки процес­сов, начиная с Si и оканчивая sn - Кольцо, помеченное набором s, будем такженазывать s-кольцом. Если t является циклическим сдвигом набора s, то Акольцо,естественно, будет тем же самым кольцом, что и s -кольцо.С каждым сообщением, которое отправляется по ходу работы алгоритма, мыассоциируем набор отличительных признаков процессов, который будем называтьтрассой данного сообщения.

Если сообщение т было отправлено процессом р,до того как р получил некоторое сообщение, то трассой сообщения т служит7.2. Кольцевые сети255набор (р). Если сообщение т было отправлено процессом р, после того как онполучил некоторое сообщение, трассой которого служит набор s = (si, . . . , s*.),то трасса сообщения т задается набором (si, . .

. , Sk, р). Сообщение с трассой sбудет называться s -сообщением. Нижняя оценка будет получена на основе ана­лиза свойств множества трасс всех сообщений, которые могут быть отправленыпо ходу работы алгоритма.Рассмотрим подмножество Е множества D. Множество Е назовем исчерпы­вающим, если выполнены следующие условия:1) Е префиксно замкнуто, т. е. tи € Е = > t € £;2) Е является циклическим покрытием множества D, т. е. Vs€Z): C S (s)n £ фф 0.Как будет показано далее, множество всех трасс любого алгоритма являет­ся исчерпывающим. Чтобы вывести отсюда нижнюю оценку сложности такогоалгоритма, определим две меры множества Е.

Будем говорить, что набор t появ­ляется как последовательный набор отличительных признаков в s -кольце, еслиt — это префикс какого-нибудь набора reC S (s). В качестве меры A/(s, Е) выби­рается количество наборов множества Е, которые появляются последовательнов s -кольце, а в качестве M^(s, Е) — количество всех таких наборов длины к, т. е.M(s,E) = \ { t e E :Mk(s,E) = \ { t e E :ttявляется префиксом некоторого набора r€CS(s)}|,является префиксом некоторого набора r€C S(s) и len(t)=k}\.Далее мы будем рассматривать произвольный алгоритм А вычисления самогомладшего отличительного признака, а запись Еа будем использовать для обо­значения множества таких наборов s, что по ходу выполнения алгоритма А наs-кольце отправляется некоторое s -сообщение.Лемма 7.10.

Если оба набора t и и содержат набор s в качестве под­строки и по ходу работы алгоритма А на t-кольце отправляется некото­рое s-сообщение, то какое-нибудь s-сообщение будет также отправленопо ходу работы алгоритма А на и-кольце.Д о к а з а т е л ь с т в о .

Отправление s -сообщения процессом Sk, где s == (si, . . . . Sk), связано причинно-следственной зависимостью только с процес­сами Si, 1 ф i ф k. Их начальное состояние в ц-кольце будет тем же самым, чтои в Окольце (здесь уместно напомнить, что размер кольца неизвестен), и, следо­вательно, все события, предшествующие отправлению рассматриваемого сооб­щения, также осуществятся и в ц-кольце.□Лемма 7.11. Множество Еа является исчерпывающим множеством.Д о к а з а т е л ь с т в о .

Чтобы убедиться в том, что Еа является префикснозамкнутым, заметим, что если А отправляет какое-нибудь s-сообщение по ходуработы на s -кольце, то это означает, что для всякого префикса t набора s алго­ритм А сначала должен был отправить ^-сообщение на том же самом s -кольце.'•Решающего задачу о выборах. — Прим, перев.Гл. 7. Алгоритмы избрания лидера256По лемме 7.10 алгоритм А, таким образом, отправляет /-сообщения на /-кольце,и, значит, / Е ЕЛ.Чтобы убедиться в том, что Е д циклически покрывает множество D, рас­смотрим некоторое вычисление алгоритма А на s -кольце. По крайней мере одинпроцесс должен принять решение относительно самого младшего отличительно­го признака, и отсюда следует (рассуждения здесь будут подобны тем, которыепроводились при доказательстве теоремы 6 . 1 1 ), что указанный процесс получилсообщение, длина трассы которого равна len{s). Эта трасса является цикличе­ским сдвигом набора s и содержится в Е д .□Лемма 7.12.

Е1о ходу работы алгоритма А на s-кольце отправляетсяне менее M(s, Е д ) сообщений.Д о к а з а т е л ь с т в о . Рассмотрим произвольный префикс /, t € Ед, цик­лического сдвига г набора s. По определению Е д некоторое /-сообщение отправ­ляется по ходу работы алгоритма А на /-кольце. Значит, оно так же отправляетсяи по ходу работы алгоритма на r -кольце, которое совпадает с s -кольцом. Сле­довательно, для каждого элемента / из множества{/е Е д : / является префиксом некоторого набора г е CS(s)}хотя бы одно /-сообщение отправляется по ходу вычисления на s -кольце, а этосвидетельствует о том, что количество обменов сообщениями в таком вычислениибудет не меньше, чем M(s, Ед).□Для всякого множества / отличительных признаков процессов обозначим вы­ражением Рег{1) множество всех перестановок множества I.

Введем запись ауеД/)для обозначения среднего числа обменов сообщениями, используемых алгорит­мом А на всех кольцах, помеченных отличительными признаками из множестваI, а запись wor^)/) для обозначения числа обменов сообщениями, используемыхв наихудшем случае. Из предшествующей леммы следует, что если множество /состоит из /V элементов, то выполняются следующие неравенства:1) aveA(l) > ^/ v '£M(s ,E a);sePer(I)2) wof4 (/) > ma xsePer(/) M(s, ЕЛ).Нижнюю оценку теперь можно установить путем анализа произвольного исчер­пывающего множества.Теорема 7.13. Сложность в среднем всякого однонаправленного алго­ритма отыскания самого младшего отличительного признака будет неменьше чем N ■Яд/.2577.2. Кольцевые сетиД о к а з а т е л ь с т в о .

Проводя усреднение по всем начальным конфигу­рациям, помеченным множеством /, мы получаем следующие соотношения:а У е д ( /) > ^M(s ,E a) =53sEPer(l)= М£E > < s .£ „ ) =sEPer(l) k=\&=1 sEPer(l)Зафиксируем k и заметим, что для каждого набора s€Per(l) имеется Л/ префиксовдлины k, которыми начинаются циклические сдвиги набора s. Так как множествоРег(1) содержит N ! перестановок, общее число таких префиксов будет достигатьвеличины N • N\. Эти префиксы можно разбить на N ■N\/k групп, в каждой изкоторых содержится k циклических сдвигов одного и того же набора.

ПосколькуЕ/1 циклически покрывает D, множество ЕА пересекается с каждой такой группой,и поэтому справедливо неравенство5 3 Mk(s,E A) > —se Per(I).Отсюда и следует оценкаN1^ m»V —V- ^ ' £k=\N ■ ЛЛ4L = Nн «-DЭтот результат свидетельствует о том, что алгоритм Ченя—Робертса явля­ется оптимальным, если речь идет о сложности в среднем. Оценка сложностив наихудшем случае будет, по крайней мере, не меньше, чем оценка сложностив среднем, а это означает, что самая точная оценка сложности в наихудшем слу­чае расположена между величиной yV-H^~0.69A^logA^ и величиной 1.3567V log TV.Доказательство, приведенное в этом параграфе, существенно опирается надопущения о том, что кольцо является однонаправленным, и что размер кольцанеизвестен.

Нижняя оценка \^N ■была получена Бодлаендером в работе [31]для сложности в среднем алгоритмов решения задачи о выборах на двунаправ­ленных кольцах при условии, что размер кольца неизвестен. Чтобы устранитьнедетерминизм в случае двунаправленных колец, пришлось рассматривать вы­числения, в которых каждый процесс начинает работу в одно и то же время, акаждое сообщение имеет одну и ту же задержку при передаче. Для случая, когдаразмер кольце известен, Бодлаендер [32] получил нижнюю оценку - NlogN наоднонаправленных кольцах и ^ —e^/VH^ на двунаправленных кольцах (в обоихслучаях речь идет о сложности в среднем).258Гл. 7.

Алгоритмы избрания лидераПодводя итоги, заметим, что почти все сделанные нами допущения не влияютна сложность выборов на кольце. Независимо от того, известен или неизвестенразмер кольца, является ли кольцо однонаправленным или двунаправленным,рассматривается ли средний или наихудший случай, всякий раз сложность со­ставляет величину ©(TVlogjV). Здесь существенно то, что кольцо асинхронно;как будет показано в гл. 1 2 , для сетей, имеющих доступ к глобальному времени,сложность по числу обменов сообщениями будет меньше.Так как лидера можно избрать по ходу одного-единственного вычисления де­централизованного волнового алгоритма, из нижней оценки сложности выборовследует и нижняя оценка сложности для волновых алгоритмов.Следствие 7.14.

По ходу работы всякого децентрализованного алго­ритма на кольцевых сетях происходит обмен, по меньшей мере, Q(jVlogiV)сообщениями, как в среднем, так и в наихудшем случае.7.3. Произвольные сетиТеперь перейдем к изучению задачи о выборах для сетей произвольной, за­ранее неизвестной топологии при условии отсутствия сведений о соседях. Далеемы установим нижнюю оценку Q(jVlogiV+|£|) числа обменов сообщениями. Приобосновании ее мы будем сочетать идеи доказательства теоремы 6 . 6 и результа­ты предыдущего параграфа. В § 7.3.1 будет приведен простой алгоритм, имеющиймалую сложность по времени, но большую сложность по числу обменов сообще­ниями в наихудшем случае.

В §7.3.2 будет представлен алгоритм, являющийсяоптимальным по сложности в наихудшем случае.Теорема 7.15. Всякий алгоритм избрания лидера на основе сравнениядля произвольных сетей имеет сложность {и в среднем, и в наихудшемслучае), не меньшую чем 0 (|£ | + N\ogN).Д о к а з а т е л ь с т в о . Слагаемое f2(7Vlog TV) служит нижней оценкой, по­тому что произвольные сети включают в себя и кольца, для которых соблюдаетсянижняя оценка fl(NlogN).

Чтобы убедиться в том, что |£| обменов сообщениямислужит нижней оценкой даже для самого лучшего из всех вычислений, допу­стим, что некоторый алгоритм избрания А допускает вычисление С на сети G,в ходе которого осуществляется обмен менее чем |£| сообщениями (см. рис. 7.8).Построим сеть G ' , соединив две копии сети G ребром, связывающим два узла,которые вставлены в каждой копии сети G посреди ребра, не задействованногов вычислении С. Отличительные признаки в обеих частях построенной сети со­храняют тот же относительный порядок, что и в сети G.

Вычисление С можнопромоделировать совместно в обеих частях сети G', и, таким образом, мы получимвычисление, в результате которого лидерами будут избраны два процесса.□Следствие 7.16. Всякий децентрализованный волновой алгоритм дляпроизвольных сетей без предварительной осведомленности о соседях име­ет сложность по числу обменов сообщениями, не меньшую чем fi(|£|+AMogyV).7.3. Произвольные сети259Рис. 7.8. Вычисление, приводящее к двум лидерам7.3.1.

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

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