Распределенные алгоритмы (стр. 56 из 85)

Доказательство. Посылка процессом s_k s-сообщения, где s = (s₁, ..., s_k), каузально зависит только от процессов с s₁ по s_k. Их начальное состояние в u-кольце совпадает с состоянием в t-кольце (напоминаем, что размер кольца неизвестен), и следовательно совокупность событий, предшествующих посылке сообщения, также выполнима и в u-кольце.

Лемма 7.11 E_A - полное множество.

Доказательство. Чтобы показать, что E_A циклически замкнуто, заметим, что если A посылает s-сообщение при выполнении на s-кольце, тогда для любого префикса t последовательности s A сначала посылает t-сообщение на s-кольце. По Лемме 7.10 A посылает t-сообщение на t-кольце, следовательно t Î E_A.

Чтобы показать, что E_A циклически покрывает D, рассмотрим вычисление A на s-кольце. Хотя бы один процесс выбирает наименьший идентификатор, откуда следует (аналогично доказательству Теоремы 6.11), что этот процесс получил сообщение со следом длины len(s). Этот след является циклическим сдвигом s и принадлежит E.

Лемма 7.12 В вычислении на s-кольце алгоритм A посылает не менее M(s,E_A) сообщений.

Доказательство. Пусть t Î E_A - префикс циклического сдвига r последовательности s. Из определения E_A, A посылает t-сообщение в вычислении на t-кольце, а следовательно также и на r-кольце, которое совпадает с s-кольцом. Отсюда, для каждого t из {t Î E: t - префикс некоторого r Î CS(s)} в вычислении на s-кольце посылается хотя бы одно t-сообщение, что доказывает, что количество сообщений в таком вычислении составляет не менее M(s,E).

Для конечного множества I идентификаторов процессов обозначим через Per(I) множество всех перестановок I. Обозначим через ave_A(I) среднее количество сообщений, используемых A во всех кольцах, помеченных идентификаторами из I, а через wor_A(I) - количество сообщений в наихудшем случае. Из предыдущей леммы следует, что если I содержит N элементов, то

(1) ; и

(2) .

Теперь нижнюю границу можно вывести путем анализа произвольных полных множеств.

Теорема 7.13 Средняя сложность однонаправленного алгоритма поиска наименьшего идентификатора составляет не менее N*H_N.

Доказательство. Усредняя по всем начальным конфигурациям, помеченным множеством I, мы находим

Зафиксируем k и отметим, что для любого s Î Per(I) существует N префиксов циклических сдвигов s длины k. N! перестановок в Per(I) увеличивают количество таких префиксов до N*N!. Их можно сгруппировать в N*N!/k групп, каждая из которых содержит по k циклических сдвигов одной последовательности. Т.к. E_A циклически покрывает D, E_A пересекает каждую группу, следовательно .

Отсюда следует.

Этот результат означает, что алгоритм Чанга-Робертса оптимален, когда рассматривается средний случай. Сложность в наихудшем случае больше или равна сложности в среднем случае, откуда следует, что наилучшая достижимая сложность для наихудшего случая находится между N*H_N » 0.69N logN и » 0.356N logN.

Доказательство, данное в этом разделе, в значительной степени полагается на предположения о том, что кольцо однонаправленное и его размер неизвестен. Нижняя граница, равная 0.5N*H_N была доказана Bodlaender [Bod88] для средней сложности алгоритмов выбора на двунаправленных кольцах, где размер кольца неизвестен. Чтобы устранить недетерминизм из двунаправленного кольца, рассматриваются вычисления, в которых каждый процесс начинается в одно и то же время и все сообщения имеют одинаковую задержку передачи. Для случая, когда размер кольца известен, Bodlaender [Bod91a] вывел нижнюю границу, равную 0.5N logN для однонаправленных колец и (1/4-e)N*H_N для двунаправленных колец (обе границы для среднего случая).

В итоге оказывается, что сложность выбора на кольце не чувствительна практически ко всем предположениям. Независимо от того, известен или нет размер кольца, однонаправленное оно или двунаправленное, рассматривается ли средний или наихудший случай, - в любом случае сложность составляет Q(N logN). Существенно важно, что кольцо асинхронно; для сетей, где доступно глобальное время, сложность сообщений ниже, как будет показано в Главе 11.

Т.к. лидер может быть выбран за одно выполнение децентрализованного волнового алгоритма, из нижней границы для выбора следует нижняя граница для волновых алгоритмов.

Заключение 7.14 Любой децентрализованный волновой алгоритм для кольцевых сетей передает не менее W(N logN) сообщений, как в среднем, так и в наихудшем случае.

Рис.7.8

7.3 Произвольные Сети

Теперь изучим проблему выбора для сетей произвольной, неизвестной топологии без знания о соседях. Нижняя граница Ω(N logN+½E½) сообщений будет показана ниже. Доказательство объединяет идею Теоремы 6.6 и результаты предыдущего подраздела. В Подразделе 7.3.1 будет представлен простой алгоритм, который имеет низкую сложность по времени, но высокую сложность по сообщениям в худшем случае. В Подразделе 7.3.2 будет представлен оптимальный алгоритм для худшего случая.

Теорема 7.15 Любой сравнительный алгоритма выбора для произвольных сетей имеет (в худшем и среднем случае) сложность по сообщения по крайней мере Ω(Nlog N + ½E½).

Рисунок 7.8 вычисление с двумя ЛИДЕРАМИ.

Доказательство. Граница Ω(N log N + ½E½) является нижней, потому что произвольные сети включают кольца, для которых нижняя граница Ω(N logN). Чтобы видеть, что ½E½ сообщений является нижней границей, даже в лучшем из всех вычислений, предположим что, алгоритм выбора имеет вычисление С на сети G, в котором обменивается менее чем ½E½ сообщений ; см. Рисунок 7.8. Построим сеть G ', соединяя две копии G одним ребром между узлами, связанными ребром , которое не используется в C. Тождественные части сети имеют тот же самый относительный порядок как и в G. Вычисление С может моделироваться одновременно в обеих частях G ', выдавая вычисление, в котором два процесса станут избранными. -

Заключение 7.16 Децентрализованный волновой алгоритм для произвольных сетей без знания о соседях имеет сложность по сообщения по крайней мере Ω(NlogN + ½E½).

7.3.1 Вырождение и Быстрый Алгоритм

Алгоритм для выбора лидера может быть получен из произвольного централизованного волнового алгоритма применением преобразования называемого вырождением. В полученном алгоритме выбора каждый инициатор начинает отдельную волну; все сообщения волны, начатой процессом p должны быть помечены идентификатором p, чтобы отличить их от сообщений различных волн. Алгоритм гарантирует, что, независимо от того, сколько волн начато, только одна волна будет бежать к решению, а именно, волна самого маленького инициатора. Все другие волны будут прерваны прежде, чем решение может иметь место.

Для волнового алгоритма A, алгоритм выбора Ex(A) следующий. В каждый момент времени каждый процесс активен не более чем в одной волне ; эта волна - текущая активная волна, обозначенная caw , с начальным значением udef. Инициаторы выбора действуют, как будто они начинают волну и присваивают caw их собственный идентификатор . Если сообщение некоторой волны, скажем волны, которую начал q, достигает p, p обрабатывает сообщение следующим образом.

var caw_p : P init udef ; (* текущая активная волна *)

rec_p : integer init 0 ; (* число полученных átok, caw_pñ *)

father_p : P init udef ; (* отец в волне caw_p *)

lrec_p : integer init 0 ; (* число полученных áldr, . ñ *)

win_p: P init udef; (* идентификатор лидера*)

begin if p is initiator then

begin caw_p := p;

forall q Î Neigh_p do send á tok, pñ to q

end;

while lrec_p < #Neigh_p do

begin receive msg from q ;

if msg = á ldr, r ñ then

begin if lrec_p = 0 then

forall q Î. Neigh_p do send á ldr, r ñ to q ;

lrec_p := lrec_p + 1 ; win_p := r

end

else (* сообщение á tok, rñ *)

begin if r < caw_p then (* Переинициализируем алгоритм*)

begin caw_p := r , rec_p := 0 , father_p :== q ;

forall sÎ Neigh_p , s ¹ q

do send á tok, r ñ to s

end;

if r = caw_p then

begin rec_p := rec_p + 1 ;

if rec_p = #Neigh_p then

if caw_p = p

then forall s Î Neigh_p do send á ldr, p ñ to s

else send á tok, cawpñ to father_p

end

(* если r > caw_p сообщение игнорируется*)

end

end;

if win_p = p then state_p :== leader else state_p :== lost

end

Алгоритм 7.9 Вырождение примененное к алгоритму эха.

Если q> caw_p, сообщение просто игнорируется, эффективно приводя волну q к неудаче. Если с q = caw_p, с сообщением поступают в соответствии с волновым алгоритмом. Если q < caw_p или caw_p = udef, p присоединяется к выполнению волны q, повторно присваивая переменным их начальные значения и присваивая caw_p значение q. Когда волна, начатая q выполняет событие решения (в большинстве волновых алгоритмов, это решение всегда имеет место в q), q будет избран. Если волновой алгоритм такой, что решающий узел не обязательно равен инициатору, то решающий узел информирует инициатора через дерево охватов(остовное дерево) как определено в Lemma 6.3. При этом требуется не более N - 1 сообщений; мы игнорируем их в следующей теореме.