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

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

Далее предполагается, что 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 получил <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 процессов “выкрикивают” сообщение голосования.

Страницы: 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