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

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

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

Соглашение о подмножестве корректных процессов. Сначала представляется алгоритм Фишера, Линча и Патерсона [FLP], с помощью которого каждый из корректных процессов вычисляет одну и ту же совокупность корректных процессов. Способность восстановления этого алгоритма ; пусть равно , и заметим, что корректных процессов по меньшей мере . Алгоритм работает в два этапа; см. Алгоритм 13.1.

Заметим, что процессы посылают сообщения сами себе; это делается во многих устойчивых алгоритмах и облегчает анализ. Здесь и в дальнейшем, операция “shout<mes>” означает

forall do send<mes> to .

Эти процессы строят ориентированный граф , “выкрикивая” свой идентификатор (в сообщении <name, >) и ожидая приема сообщений. Так как корректных процессов по меньшей мере , каждый корректный процесс получает достаточно много сообщений для завершения этой части. Преемники в графе - вершины , из которых получил сообщение <name, >.

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

Следовательно, на втором этапе алгоритма, процессы образуют индуцированный подграф графа , содержащий по меньшей мере их потомков, получая множество преемников от каждого процесса, который, как они знают, корректен. Так как процессы не отказвыают после посылки сообщения, на этом этапе не возникает тупика. Действительно, ждет сообщения от только если на первом этапе некоторый процесс получил сообщение <name, >, показывающее на корректность .

После завершения Алгоритма 13.1 каждый корректный процесс получил набор преемников каждого из своих потомков, позволяя таким образом вычислить уникальный узел в G.

Согласие и выбор. Поскольку все корректные процессы договариваются об узле корректных процессов, избрать процесс теперь тривиально; избирается процесс с самым большим идентификатором в K. Теперь так же просто достигнуть согласия. Каждый процесс вещает, вместе со своими преемниками, свой вход (x). После вычисления K, процессы принимают решение о значении, которое является функцией совокупности входов в K (например, значение, которое встречается наиболее часто, ноль в случае ничьей).

Алгоритмы узел-соглашения, согласия, и выбора обменивают сообщениями, где сообщение может содержать список из L имен процессов. Были предложены более эффективные алгоритмы выбора. Итаи и другие [IKWZ90] привели алгоритм, использующий сообщения и показали, что это является нижней границей. Масузава и другие [MNHT89] рассмотрели проблему для клик с чувством направления и предложили алгоритм сообщений, который также является оптимальным.

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

13.3 Детерминированно Достижимые Случаи

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

Распределенная задача описывается множествами возможных входных и выходных значений X и D, и (возможно частичным) отображением

.

Интерпретация отображения T: если вектор описывает вход процессов, то - набор допустимых выходов алгоритма, описанный как вектор решения . Если T - частичная функция, допустима не каждая комбинация входных значений.

Определение 13.10 Алгоритм является t-аварийно устойчивым решением для задачи T если он удовлетворяет следующим утверждениям.

1. Завершение. В каждом t-аварийно законном выполнении, все корректные процессы принимают решение.

2. Непротиворечивость. Если все процессы корректны, вектор решения находится в .

Условие непротиворечивости подразумевает, что в выполнении, где подмножество процессов принимает решение, частичный вектор решений всегда можно расширить до вектора в . Множество обозначает совокупность всех векторов выхода, то есть, диапазон T.

1. Пример: согласие. Проблема согласия требует, чтобы все решения были равны, т.е.,

.

1. Пример: выбор. Проблема выбора требует, чтобы один процесс принял решение 1, а другие 0, т.е.,

.

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

.

1. Пример: переименование. В проблеме переименования каждый процесс имеет отдельный идентификатор, который может браться из произвольно большой области. Каждый процесс должен принять решение о новом имени, из меньшей области 1, ..., K, так, чтобы все новые имена различались.

.

В сохраняющей порядок версии проблемы переименования, новые имена должны сохранять порядок старых имен, то есть, .

13.3.1 Разрешимая Проблема: Переименование

В этом подразделе будет представлен алгоритм для переименования Аттийи и других [ABND+90]. Алгоритм допускает до аварий (t - параметр алгоритма) и осуществляет переименование в пространстве имен размера .

Верхняя граница t. Мы сначала покажем, что никакой алгоритм переименования не сможет выдержать N/2 или большее количество сбоев; фактически, почти все аварийно-устойчивые алгоритмы имеют ограничение t

Теорема 13.11 При алгоритмов для переименования не существует.

Доказательство. Если , можно сформировать две непересекающихся группы процессов S и T размера N-t. Вследствие возможности сбоя t процессов, группа должна уметь принимать решение "самостоятельно", то есть, без взаимодействия с процессами вне группы (см. Утверждение 13.4). Но тогда группы могут независимо достичь решения в одиночном выполнении; сложный момент доказательства - показать, что эти решения могут быть взаимно противоречивы. Мы продолжим формальную аргументацию для случая переименования.

По утверждению 13.4, для каждой начальной конфигурации существует конфигурация такая, что все процессы в S приняли решение и ; то же справедливо и для T. Действие алгоритма внутри группы из N-t процессов определяет отношение векторов из N-t начальных идентификаторов к векторам из N-t новых имен. Так как начальное пространство имен неограниченно, и новые имена получаются из ограниченного диапазона, то имеются непересекающиеся входы, которые отображаются на перекрывающиеся выходы. То есть, имеются входные векторы (длины N-t) и такие, что для всех i, j, но им соответствуют векторы выхода и такие, что , для некоторых i, j.

Некорректное выполнение теперь создается следующим образом. Начальная конфигурация имеет входы в группе S и в группе T; заметьте, что все начальные имена различны (начальные имена вне обеих групп могут быть выбраны произвольно). Пусть - последовательность шагов, которыми группа T достигает, из , конфигурации , в которой процессы в T остановились (приняли решение) на именах . По утверждению 13.1, эта последовательность все еще применима в конфигурации , в которой процессы в S остановились на именах . В , два процесса остановились на одном и том же имени (потому что ), что указывает на противоречивость алгоритма. 

Далее предполагается, что t < N/2.

var : set of identities;

: integer;

begin ; : = 0; shout <set, >;

while true

do begin receive<set, V>

if then

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 получил > от N-t процессов и r получил <set, > от N-t процессов. Так как 2(N-t) > N, то есть по крайней мере один процесс, допустим p, от которого q получил > и r получил >. Следовательно, как так и - значения , что означает, что одно включено в другое. 

Лемма 13.13 Каждый корректный процесс по крайней мере однажды достигает устойчивого множества в каждом законном t-аварийном выполнении.

Доказательство. Пусть p - корректный процесс; множество может только расширяться, и содержит самое большее N входных имен. Следовательно, для достигается максимальное значение . Процесс p “выкрикивает” это значение, и сообщение <set, > получается каждым корректным процессом, что показывает, что каждый корректный процесс в конечном счете имеет надмножество .

Однако, это надмножество не строгое; иначе корректный процесс послал бы строгое надмножество к p, что противоречит выбору (как самого большого множества когда-либо побывавшего в p). Следовательно, каждый корректный процесс q имеет значение по крайней мере один раз при выполнении, и следовательно каждый корректный процесс посылает p сообщение <set, > в течение выполнения. Все эти сообщения получаются при выполнении, и, поскольку никогда не увеличивается за пределы , они все подсчитываются и заставляют стать устойчивым в p. 

После достижения устойчивого множества 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 имеют различный ранг в множестве, что снова показывает, что их решения различны. 

Обсуждение. Заметьте, что процесс не завершает Алгоритм 13.2 после принятия решения о своем имени; он продолжает алгоритм, чтобы "помочь" другим процессам тоже принять решение. Aттийя и другие [ABND+90] показывают, что это необходимо, потому что алгоритм должен справиться с ситуацией, когда некоторые процессы настолько медленны, что выполняют первый шаг после того, как некоторые другие процессы уже приняли решение.

Простой алгоритм, представленный здесь не самый лучший в отношении размера пространства имен, используемого для переименования. Aттийя и другие [ABND+90] привели более сложный алгоритм, который назначает имена в диапазоне от 1 до N + t. Результаты следующего подраздела предполагают нижнюю границу размера нового пространства имен для аварийно-устойчивого переименования N + 1.

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

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