ref (664672), страница 42

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

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

Aттийя и другие предложили также алгоритм для переименования, сохраняющего порядок. Он осуществляет переименование на целые числа в диапазоне от 1 до , что, как было показано, является самым маленьким размером пространства имен, позволяющего t-аварийно-устойчивое переименование, сохраняющее порядок.

13.3.2 Расширение Результатов Невозможности

Результат о невозможности согласия (Теорема 13.8) был обобщен Мораном и Вольфшталом [MW87] для более общих проблем решения. Граф решения задачи T - граф , где и

E = {( , ): и отличаются точно в одном компоненте}.

Задача T называется связной, если - связный граф, и несвязной иначе. Моран и Вольфштал предположили, что входной граф задачи T (определенный аналогично графу решения) связный, то есть, как в доказательстве Леммы 13.6 мы можем двигаться между любыми двумя входными конфигурациями, изменяя по порядку входы процесса. Кроме того, результат невозможности был доказан для не-тривиальных алгоритмов, то есть, алгоритмов, которые удовлетворяют, в дополнение к (1) завершению и (2) непротиворечивости,

1. Нетривиальность. Для каждого имеется достижимая конфигурация, в которой процессы остановились на (приняли решение) .

Теорема 13.15 Нетривиального 1-аварийно-устойчивого алгоритма решения для несвязной задачи T не существует.

Доказательство. Предположим, напротив, что такой алгоритм, A, существует; из него можно получить алгоритм согласия А', что противоречит Теореме 13.8. Чтобы упростить аргументацию, мы полагаем, что содержит два связных компонента, "0" и "1".

Алгоритм А’ сначала моделирует A, но вместо того, чтобы остановиться на значении d, процесс “выкрикивает” <vote, d> и ждет получения N-1 сообщений голосования. Тупика не возникает, потому что все корректные процессы принимают решение в A; следовательно по крайней мере N-1 процессов “выкрикивают” сообщение голосования.

После получения сообщений, у процесса p есть N-l компонентов вектора в . Этот вектор можно расширить значением процесса, от которого голос не был получен так, чтобы весь вектор находился в . (Действительно, непротиворечивое решение принято этим процессом, или все еще возможно.)

Теперь заметим, что различные процессы могут вычислять различные расширения, но эти расширения принадлежат одному и тому же связному компоненту графа . Каждый процесс, который получил N-1 голосов, останавливается на (принимает решение) имени связанного компонента, которому принадлежит расширенный вектор. Остается показать, что А' является алгоритмом согласия.

Завершение. Выше уже обсуждалось, что каждый корректный процесс получает по крайней мере N-1 голосов.

Соглашение. Мы сначала докажем, что существует вектор такой, что каждый корректный процесс получает N-1 компонентов .

Случай 1: Все процессы нашли решение в A. Пусть будет вектором достигнутых решений; каждый процесс получает N-1 компонентов , хотя "недостающий" компонент может быть различным для каждого процесса.

Случай 2: Все процессы за исключением одного, допустим r, нашли решение в A. Все корректные процессы получают одни и те же N-1 решений, а именно решения всех процессов за исключением r. Возможно, что r потерпел аварию, но, так как возможно , что r просто очень медленный, он все же сможет достичь решения, то есть, существует вектор , который расширяет решения, принятые на настоящий момент.

Из существования следует, что каждый процесс принимает решение о связном компоненте этого вектора.

Нетривиальность. Из нетривиальности A, можно достичь векторы решения как в компоненте 0, так и в компоненте 1; по построению А’ оба решения возможны.

Таким образом, А' является асинхронным, детерминированным, 1-аварийно-устойчивым алгоритмом согласия. Алгоритма А не существует по Теореме 13.8. 

Обсуждение. Требование нетривиальности, утверждающее, что каждый вектор решения в достижим, является довольно сильным. Можно спросить, могут ли некоторые алгоритмы, которые являются тривиальными в этом смысле тем не менее быть интересными. В качестве примера, рассмотрим Алгоритм 13.2 для переименования; с ходу не видно, что он нетривиален, то есть, каждый вектор с отдельным именем достижим (да, достижим); еще менее понятно то, почему нетривиальность может представлять интерес в этом случае.

Исследование доказательства Теоремы 13.15 показывает, что в доказательстве можно использовать более слабое требование нетривиальности, а именно, что векторы решения достижимы по крайней мере в двух различных связных компонентах . Такую ослабленную нетривиальность можно иногда вывести из формулировки проблемы.

Фундаментальная работа о задачах решения, которые являются разрешимыми и неразрешимыми при наличии одного сбойного процессора, была выполнена Бираном, Мораном и Заксом [BMZ90]. Они дали полную комбинаторную характеристику разрешимых задач решения.

13.4 Вероятностные Алгоритмы Согласия

В доказательстве Теоремы 13.8 показано, что каждый асинхронный алгоритм согласия имеет бесконечные выполнения, в которых никакое решение не принимается. К счастью, для хорошо подобранных алгоритмов такие выполнения могут быть достаточно редки и иметь вероятность 0, что делает алгоритмы очень полезными в вероятностном смысле; см. Главу 9. В этом разделе мы представляем два вероятностных алгоритма согласия, один для модели аварий, другой для Византийской модели; алгоритмы были предложены Брахой и Туэгом [BT85]. В обоих случаях сначала доказывается верхний предел для способности восстановления (t < N/2 и t < N/3, соответственно) и что и оба алгоритма удовлетворяют соответствующей границе.

В требованиях правильности для этих вероятностных алгоритмов согласия, требование завершения сделано вероятностным, то есть, заменено более слабым требованием сходимости.

1. Сходимость. Для каждой начальной конфигурации,

[корректный процесс не принял решение после k шагов] = 0.

Частичная правильность (Соглашение) должна удовлетворяться при каждом выполнении; возникающие в результате вероятностные алгоритмы имеют класс Las Vegas (Подраздел 9.1.2).

Вероятность принимается всеми выполнениями, начинающимися в данной начальной конфигурации. Чтобы вероятности были значимыми, должно быть задано распределение вероятности над этими выполнениями. Это можно сделать использованием рандомизации в процессах (как в Главе 9), но здесь вместо этого определяется распределение вероятности на прибытиях сообщений.

Распределение вероятности на выполнениях, начинающихся в данной начальной конфигурации, определяется предположением о законном планировании. Оба алгоритма функционируют в раундах; в раунде процесс “выкрикивает” сообщение и ждет получения N-t сообщений. Определим R(q, p, k) как событие, когда в раунде k процесс p получает (раунд-k) сообщение q среди первых N-t сообщений. Законное планирование означает, что

1. .

2. Для всех k и различных процессов p, q, r, события R(q, p, k) и R(q, r, k) независимы.

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

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

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

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

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

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

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

Для подмножества процессов 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 могут достигать решения независимо; если возможны различные решения, можно достичь противоречивой конфигурации, объединяя планы. 

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

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

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

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

Список файлов реферата