В итоге оказывается, что сложность выбора на кольце не чувствительна практически ко всем предположениям. Независимо от того, известен или нет размер кольца, однонаправленное оно или двунаправленное, рассматривается ли средний или наихудший случай, - в любом случае сложность составляет 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 ', выдавая вычисление, в котором два процесса станут избранными. o
Заключение 7.16 Децентрализованный волновой алгоритм для произвольных сетей без знания о соседях имеет сложность по сообщения по крайней мере Ω(NlogN + ½E½).
7.3.1 Вырождение и Быстрый Алгоритм
Алгоритм для выбора лидера может быть получен из произвольного централизованного волнового алгоритма применением преобразования называемого вырождением. В полученном алгоритме выбора каждый инициатор начинает отдельную волну; все сообщения волны, начатой процессом p должны быть помечены идентификатором p, чтобы отличить их от сообщений различных волн. Алгоритм гарантирует, что, независимо от того, сколько волн начато, только одна волна будет бежать к решению, а именно, волна самого маленького инициатора. Все другие волны будут прерваны прежде, чем решение может иметь место.
Для волнового алгоритма A, алгоритм выбора Ex(A) следующий. В каждый момент времени каждый процесс активен не более чем в одной волне ; эта волна - текущая активная волна, обозначенная caw , с начальным значением udef. Инициаторы выбора действуют, как будто они начинают волну и присваивают caw их собственный идентификатор . Если сообщение некоторой волны, скажем волны, которую начал q, достигает p, p обрабатывает сообщение следующим образом.
var cawp : P init udef ; (* текущая активная волна *)
recp : integer init 0 ; (* число полученных átok, cawp ñ *)
fatherp : P init udef ; (* отец в волне cawp *)
lrecp : integer init 0 ; (* число полученных áldr, . ñ *)
winp : P init udef; (* идентификатор лидера*)
begin if p is initiator then
begin cawp := p;
forall q Î Neighp do send á tok, pñ to q
end;
while lrecp < #Neighp do
begin receive msg from q ;
if msg = á ldr, r ñ then
begin if lrecp = 0 then
forall q Î. Neighp do send á ldr, r ñ to q ;
lrecp := lrecp + 1 ; winp := r
end
else (* сообщение á tok, rñ *)
begin if r < cawp then (* Переинициализируем алгоритм*)
begin cawp := r , recp := 0 , fatherp :== q ;
forall sÎ Neighp , s ¹ q
do send á tok, r ñ to s
if r = cawp then
begin recp := recp + 1 ;
if recp = #Neighp then
if cawp = p
then forall s Î Neighp do send á ldr, p ñ to s
else send á tok, cawpñ to fatherp
(* если r > cawp сообщение игнорируется*)
if winp = p then statep :== leader else statep :== lost
Алгоритм 7.9 Вырождение примененное к алгоритму эха.
Если q> cawp, сообщение просто игнорируется, эффективно приводя волну q к неудаче. Если с q = cawp, с сообщением поступают в соответствии с волновым алгоритмом. Если q < cawp или cawp = udef, p присоединяется к выполнению волны q, повторно присваивая переменным их начальные значения и присваивая cawp значение q. Когда волна, начатая q выполняет событие решения (в большинстве волновых алгоритмов, это решение всегда имеет место в q), q будет избран. Если волновой алгоритм такой, что решающий узел не обязательно равен инициатору, то решающий узел информирует инициатора через дерево охватов(остовное дерево) как определено в Lemma 6.3. При этом требуется не более N - 1 сообщений; мы игнорируем их в следующей теореме.
Теорема 7.17. Если А - централизованный волновой алгоритм, использующий М сообщений на одну волну, алгоритм Ex(A), выбирает лидера использую не более NM сообщений.
Доказательство. Пусть p0 самый маленький инициатор. К волне, начатой p0 немедленно присоединяются все процессы, которые получают сообщение этой волны, и каждый процесс заканчивает эту волну, потому что нет волны с меньшим идентификатором, для которой процесс прервал бы выполнение волны p0. Следовательно, волна p0 бежит к завершению, решение будет иметь место, и p0 становится лидером.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90
