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

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

(* т.е.: forall do send<name, > to *)

while < L

do begin receive<name, >; end;

shout<pre, , >;

;

while

do begin receive<pre, , >;

;

end;

Вычислить узел в G

end

Алгоритм 13.1 Вычисление узла.

Так как процессы не отказывают после посылки сообщения, то для процесса безопасно ждать приема сообщения от , зная, что уже послал по меньшей мере одно сообщение. Будет показано, что проблемы согласия и выборов разрешимы в модели изначально-мертвых, пока отказывает меньшинство процессов (t < N/2). Большее число изначально-мертвых процессов не допускается (см. Упражнение 13.3).

Соглашение о подмножестве корректных процессов. Сначала представляется алгоритм Фишера, Линча и Патерсона [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) Пример: согласие. Проблема согласия требует, чтобы все решения были равны, т.е.,

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

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

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

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

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

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

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

Теорема 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 остановились на именах . В , два процесса остановились на одном и том же имени (потому что ), что указывает на противоречивость алгоритма. o