Реферат: Распределенные алгоритмы
begin ;
if and then
(* впервые не изменялось: принять решение*)
end
else if then
skip (*Игнорировать “старую” информацию*)
else (*новый вход; обновить Vp и начать счет заново*)
begin if then else ;
; shout<set, >
end
end
end
Алгоритм 13.2 Простой алгоритм переименования.
Алгоритм переименования. В алгоритме переименования (Алгоритм 13.2), процесс p сохраняет множество входов процесса, которые p видел; первоначально, содержит только . Каждый раз, когда p получает множество входов, включая те, которые являются новыми для p, расширяется новыми входами. При старте и каждый раз, когда расширяется, p “выкрикивает” свое множество. Как видно, множество растет только в течение выполнения, т.е., последующие значения полностью упорядочиваются при включении, и, кроме того, содержит самое большее N имен. Следовательно, процесс p “выкрикивает” свое множество самое большее N раз, что показывает, что алгоритм завершается и что сложность по сообщениям ограничена .
Далее, p считает (в переменной ) сколько раз он получил копии своего текущего множества . Первоначально равна 0, и увеличивается каждый раз, когда получается сообщение, содержащее . Получение сообщения <set, V> может вызвать рост , что требует сброса . Если новое значение равняется V (то есть, если V - строгое надмножество старого ), устанавливается в 1, иначе в 0.
Говорят, что процесс p, достигает устойчивого множества V если становится равным N-t, когда значение - V. Другими словами, p получил в (N-t)-й раз текущее значение V Vp.
Лемма 13.12 Устойчивые множества полностью упорядочены, то есть, если q достигает устойчивого множества и r достигает устойчивого множества , то или .
Доказательство. Предположим, что q достигает устойчивого множества и r достигает устойчивого множества . Это подразумевает, что q получил <set, > от N-t процессов и r получил <set, > от N-t процессов. Так как 2(N-t) > N, то есть по крайней мере один процесс, допустим p, от которого q получил <set, > и r получил <set, >. Следовательно, как так и - значения , что означает, что одно включено в другое. o
Лемма 13.13 Каждый корректный процесс по крайней мере однажды достигает устойчивого множества в каждом законном t-аварийном выполнении.
Доказательство. Пусть p - корректный процесс; множество может только расширяться, и содержит самое большее N входных имен. Следовательно, для достигается максимальное значение . Процесс p “выкрикивает” это значение, и сообщение <set, > получается каждым корректным процессом, что показывает, что каждый корректный процесс в конечном счете имеет надмножество .
Однако, это надмножество не строгое; иначе корректный процесс послал бы строгое надмножество к p, что противоречит выбору (как самого большого множества когда-либо побывавшего в p). Следовательно, каждый корректный процесс q имеет значение по крайней мере один раз при выполнении, и следовательно каждый корректный процесс посылает p сообщение <set, > в течение выполнения. Все эти сообщения получаются при выполнении, и, поскольку никогда не увеличивается за пределы , они все подсчитываются и заставляют стать устойчивым в p. o
После достижения устойчивого множества V впервые, процесс p останавливается на паре (s, r), где s - размер V, и r - положение в V. Устойчивый множество было получено от N-t процессов, и следовательно содержит по крайней мере N-t входных имен, что показывает . Положение в множестве размера s удовлетворяет . Число возможных решений, следовательно, , что равняется ; если нужно, можно использовать фиксированное отображение пар на целые числа в диапазоне 1,..., K (Упражнение 13.5).
Теорема 13.14 Алгоритм 13.2 решает проблему переименования с выходным пространством имен размера .
Доказательство. Так как, в любом законном t-аварийном выполнении каждый корректный процесс достигает устойчивого множества, каждый корректный процесс останавливается на новом имени. Чтобы показать, что все новые имена различны, рассмотрим устойчивые множества и , достигаемые процессами q и r соответственно. Если эти множества имеют различные размеры, решения q и r различны, потому что размер включается в решение. Если множества имеют один и тот же размер, то по Лемме 13.12, они равны; тогда q и r имеют различный ранг в множестве, что снова показывает, что их решения различны. o
Обсуждение. Заметьте, что процесс не завершает Алгоритм 13.2 после принятия решения о своем имени; он продолжает алгоритм, чтобы "помочь" другим процессам тоже принять решение. Aттийя и другие [ABND+90] показывают, что это необходимо, потому что алгоритм должен справиться с ситуацией, когда некоторые процессы настолько медленны, что выполняют первый шаг после того, как некоторые другие процессы уже приняли решение.
Простой алгоритм, представленный здесь не самый лучший в отношении размера пространства имен, используемого для переименования. Aттийя и другие [ABND+90] привели более сложный алгоритм, который назначает имена в диапазоне от 1 до N + t. Результаты следующего подраздела предполагают нижнюю границу размера нового пространства имен для аварийно-устойчивого переименования N + 1.
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. o
Обсуждение. Требование нетривиальности, утверждающее, что каждый вектор решения в достижим, является довольно сильным. Можно спросить, могут ли некоторые алгоритмы, которые являются тривиальными в этом смысле тем не менее быть интересными. В качестве примера, рассмотрим Алгоритм 13.2 для переименования; с ходу не видно, что он нетривиален, то есть, каждый вектор с отдельным именем достижим (да, достижим); еще менее понятно то, почему нетривиальность может представлять интерес в этом случае.
Исследование доказательства Теоремы 13.15 показывает, что в доказательстве можно использовать более слабое требование нетривиальности, а именно, что векторы решения достижимы по крайней мере в двух различных связных компонентах . Такую ослабленную нетривиальность можно иногда вывести из формулировки проблемы.
Страницы: 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