Быстрый поиск

Реферат: Распределенные алгоритмы

Заметьте, что Утверждение 13.4 также выполняется для вероятностных алгоритмов, когда требуется сходимость (завершение с вероятностью один). Действительно, так как достижимая конфигурация достигается с положительной вероятностью, решенная конфигурация должна быть достижима из каждой достижимой конфигурации (хотя не обязательно достигаемой в каждом выполнении).

13.4.1 Аварийно-устойчивые Протоколы Согласия

В этом подразделе изучается проблема согласия в модели аварийного отказа. Сначала доказывается верхняя граница t < N/2 способности восстановления, потом приводится алгоритм со способностью восстановления t < N/2.

Теорема 13.16 t-аварийно-устойчивого протокола согласия для не существует.

Доказательство. Существование такого протокола, допустим P, подразумевает следующий три требования.

Требование 13.17 P имеет бивалентную начальную конфигурацию.

Доказательство. Аналогично доказательству Леммы 13.6; детали оставлены читателю. o

Для подмножества процессов S, конфигурация называется S-валентной, если и 0- и 1-решенные конфигурации достижимы из с помощью только шагов в S. называется S-0-валентной если, делая шаги только в S, 0-решенная конфигурация, и никакая 1-решенная конфигурации, может быть достигнута, S-1-валентная конфигурация определяется аналогично.

Разделим процессы на две группы, S и T, размера и .

Требование 13.18 Достижимая конфигурация является или S-0-валентной и T-0-валентной, или S-1-валентной и T-1-валентной.

Доказательство. Действительно, высокая способность восстановления протокола подразумевает, что и S и T могут достигать решения независимо; если возможны различные решения, можно достичь противоречивой конфигурации, объединяя планы. o

Требование 13.19 P не имеет достижимой бивалентной конфигурации.

Доказательство. Пусть дана достижимая бивалентная конфигурация и предположим, что это S-l-валентна и T-1-валентна (используем Требование 13.18). Однако, бивалентна, поэтому (ясно из связи между группами) 0-решенная конфигурация также достижима из . В последовательности конфигураций от до имеются две последующих конфигурации и , где является и S-v-валентной и T-v-валентной. Пусть p - процесс, вызывающий переход из в . Теперь невыполнимо , потому что S-1-валентна и S-0-валентна; аналогично невыполнимо . Мы пришли к противоречию. o

Противоречие существованию протокола P является результатом Требований 13.17 и 13.19; таким образом Теорема 13.16 доказана. o

Аварийно-устойчивый алгоритм согласия Брахи и Туэга. Аварийно-устойчивый алгоритм согласия, предложенный Брахой и Туэгом [BT85] функционирует в раундах: в раунде k процесс посылает сообщение всем процессам (включая себя) и ждет получения N-t сообщений раунда k. Ожидание такого числа сообщений не представляет возможность тупика (см. Упражнение 13.10).

В каждом раунде, процесс p “выкрикивает” голос за 0 или за 1 вместе с весом. Вес - число голосов, полученных для этого значения в предыдущем раунде (1 в первом раунде); голос с весом, превышающим N/2, называется свидетелем. Хотя различные процессы в раунде могут голосовать по-разному, в одном раунде никогда нет свидетелей различных значений, как будет показано ниже. Если процесс p получает свидетеля в раунде k, p голосует за свое значение в раунде k+1; иначе p голосует за большинство полученных голосов. Решение принимается, если в раунде получено больше, чем t свидетелей; решительный процесс выходит основной цикл и свидетели криков в течение следующих двух раундов, чтобы дать возможность другим процессам решить. Протокол дан как Алгоритм 13.3.

var : (0, 1) init (*голос p*)