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

Непротиворечивость. Если все процессы корректны, вектор решения [pic]

находится в [pic].

Условие непротиворечивости подразумевает, что в выполнении, где

подмножество процессов принимает решение, частичный вектор решений всегда

можно расширить до вектора в [pic]. Множество [pic] обозначает совокупность

всех векторов выхода, то есть, диапазон T.

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

т.е.,

[pic].

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

1, а другие 0, т.е.,

[pic].

Пример: приблизительное соглашение. В проблеме [pic]-приблизительного

соглашения каждый процесс имеет действительное входное значение и принимает

решение о действительном выходном значении. Максимальное различие между

двумя значениями выхода самое большее e, и выходы должны быть заключены

между двумя входами.

[pic].

Пример: переименование. В проблеме переименования каждый процесс имеет

отдельный идентификатор, который может браться из произвольно большой

области. Каждый процесс должен принять решение о новом имени, из меньшей

области 1, ..., K, так, чтобы все новые имена различались.

[pic].

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

сохранять порядок старых имен, то есть, [pic].

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

В этом подразделе будет представлен алгоритм для переименования Аттийи и

других [ABND+90]. Алгоритм допускает до [pic] аварий (t - параметр

алгоритма) и осуществляет переименование в пространстве имен размера [pic].

Верхняя граница t. Мы сначала покажем, что никакой алгоритм переименования

не сможет выдержать N/2 или большее количество сбоев; фактически, почти все

аварийно-устойчивые алгоритмы имеют ограничение t;

while true

do begin receive

if [pic] then

begin [pic];

if [pic] and [pic] then

(*[pic] впервые не изменялось: принять решение*)

[pic]

end

else if [pic] then

skip (*Игнорировать “старую” информацию*)

else (*новый вход; обновить Vp и начать счет заново*)

begin if [pic] then [pic] else [pic];

[pic]; shout

end

end

end

Алгоритм 13.2 Простой алгоритм переименования.

Алгоритм переименования. В алгоритме переименования (Алгоритм 13.2),

процесс p сохраняет множество [pic] входов процесса, которые p видел;

первоначально, [pic] содержит только [pic]. Каждый раз, когда p получает

множество входов, включая те, которые являются новыми для p, [pic]

расширяется новыми входами. При старте и каждый раз, когда [pic]

расширяется, p “выкрикивает” свое множество. Как видно, множество [pic]

растет только в течение выполнения, т.е., последующие значения [pic]

полностью упорядочиваются при включении, и, кроме того, [pic] содержит

самое большее N имен. Следовательно, процесс p “выкрикивает” свое множество

самое большее N раз, что показывает, что алгоритм завершается и что

сложность по сообщениям ограничена [pic].

Далее, p считает (в переменной [pic]) сколько раз он получил копии своего

текущего множества [pic]. Первоначально [pic] равна 0, и увеличивается

каждый раз, когда получается сообщение, содержащее [pic]. Получение

сообщения может вызвать рост [pic], что требует сброса [pic]. Если

новое значение [pic] равняется V (то есть, если V - строгое надмножество

старого [pic]), [pic] устанавливается в 1, иначе в 0.

Говорят, что процесс p, достигает устойчивого множества V если [pic]

становится равным N-t, когда значение [pic] - V. Другими словами, p получил

в (N-t)-й раз текущее значение V Vp.

Лемма 13.12 Устойчивые множества полностью упорядочены, то есть, если q

достигает устойчивого множества [pic] и r достигает устойчивого множества

[pic], то [pic] или [pic].

Доказательство. Предположим, что q достигает устойчивого множества [pic] и

r достигает устойчивого множества [pic]. Это подразумевает, что q получил

от N-t процессов и r получил от N-t процессов.

Так как 2(N-t) > N, то есть по крайней мере один процесс, допустим p, от

которого q получил и r получил . Следовательно,

как [pic] так и [pic] - значения [pic], что означает, что одно включено в

другое. (

Лемма 13.13 Каждый корректный процесс по крайней мере однажды достигает

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

Доказательство. Пусть p - корректный процесс; множество [pic] может только

расширяться, и содержит самое большее N входных имен. Следовательно, для

[pic] достигается максимальное значение [pic]. Процесс p “выкрикивает” это

значение, и сообщение получается каждым корректным процессом,

что показывает, что каждый корректный процесс в конечном счете имеет

надмножество [pic].

Однако, это надмножество не строгое; иначе корректный процесс послал бы

строгое надмножество [pic] к p, что противоречит выбору [pic] (как самого

большого множества когда-либо побывавшего в p). Следовательно, каждый

корректный процесс q имеет значение [pic] по крайней мере один раз при

выполнении, и следовательно каждый корректный процесс посылает p сообщение

в течение выполнения. Все эти сообщения получаются при

выполнении, и, поскольку [pic] никогда не увеличивается за пределы [pic],

они все подсчитываются и заставляют [pic] стать устойчивым в p. (

После достижения устойчивого множества V впервые, процесс p останавливается

на паре (s, r), где s - размер V, и r - положение [pic] в V. Устойчивый

множество было получено от N-t процессов, и следовательно содержит по

крайней мере N-t входных имен, что показывает [pic]. Положение в множестве

размера s удовлетворяет [pic]. Число возможных решений, следовательно,

[pic], что равняется [pic]; если нужно, можно использовать фиксированное

отображение пар на целые числа в диапазоне 1,..., K (Упражнение 13.5).

Теорема 13.14 Алгоритм 13.2 решает проблему переименования с выходным

пространством имен размера [pic].

Доказательство. Так как, в любом законном t-аварийном выполнении каждый

корректный процесс достигает устойчивого множества, каждый корректный

процесс останавливается на новом имени. Чтобы показать, что все новые имена

различны, рассмотрим устойчивые множества [pic] и [pic], достигаемые

процессами q и r соответственно. Если эти множества имеют различные

размеры, решения q и r различны, потому что размер включается в решение.

Если множества имеют один и тот же размер, то по Лемме 13.12, они равны;

тогда q и r имеют различный ранг в множестве, что снова показывает, что их

решения различны. (

Обсуждение. Заметьте, что процесс не завершает Алгоритм 13.2 после принятия

решения о своем имени; он продолжает алгоритм, чтобы "помочь" другим

процессам тоже принять решение. Aттийя и другие [ABND+90] показывают, что

это необходимо, потому что алгоритм должен справиться с ситуацией, когда

некоторые процессы настолько медленны, что выполняют первый шаг после того,

как некоторые другие процессы уже приняли решение.

Простой алгоритм, представленный здесь не самый лучший в отношении размера

пространства имен, используемого для переименования. Aттийя и другие

[ABND+90] привели более сложный алгоритм, который назначает имена в

диапазоне от 1 до N + t. Результаты следующего подраздела предполагают

нижнюю границу размера нового пространства имен для аварийно-устойчивого

переименования N + 1.

Aттийя и другие предложили также алгоритм для переименования, сохраняющего

порядок. Он осуществляет переименование на целые числа в диапазоне от 1 до

[pic], что, как было показано, является самым маленьким размером

пространства имен, позволяющего t-аварийно-устойчивое переименование,

сохраняющее порядок.

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

Результат о невозможности согласия (Теорема 13.8) был обобщен Мораном и

Вольфшталом [MW87] для более общих проблем решения. Граф решения задачи T -

граф [pic], где [pic] и

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

Задача T называется связной, если [pic]- связный граф, и несвязной иначе.

Моран и Вольфштал предположили, что входной граф задачи T (определенный

аналогично графу решения) связный, то есть, как в доказательстве Леммы 13.6

мы можем двигаться между любыми двумя входными конфигурациями, изменяя по

порядку входы процесса. Кроме того, результат невозможности был доказан для

не-тривиальных алгоритмов, то есть, алгоритмов, которые удовлетворяют, в

дополнение к (1) завершению и (2) непротиворечивости,

Нетривиальность. Для каждого [pic] имеется достижимая конфигурация, в

которой процессы остановились на (приняли решение) [pic].

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

несвязной задачи T не существует.

Доказательство. Предположим, напротив, что такой алгоритм, A, существует;

из него можно получить алгоритм согласия А', что противоречит Теореме 13.8.

Чтобы упростить аргументацию, мы полагаем, что [pic] содержит два связных

компонента, "0" и "1".

Алгоритм А’ сначала моделирует A, но вместо того, чтобы остановиться на

значении d, процесс “выкрикивает” и ждет получения N-1 сообщений

голосования. Тупика не возникает, потому что все корректные процессы

принимают решение в A; следовательно по крайней мере N-1 процессов

“выкрикивают” сообщение голосования.

После получения сообщений, у процесса p есть N-l компонентов вектора в

[pic]. Этот вектор можно расширить значением процесса, от которого голос не

был получен так, чтобы весь вектор находился в [pic]. (Действительно,

непротиворечивое решение принято этим процессом, или все еще возможно.)

Теперь заметим, что различные процессы могут вычислять различные

расширения, но эти расширения принадлежат одному и тому же связному

компоненту графа [pic]. Каждый процесс, который получил N-1 голосов,

останавливается на (принимает решение) имени связанного компонента,

которому принадлежит расширенный вектор. Остается показать, что А' является

алгоритмом согласия.

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

крайней мере N-1 голосов.

Соглашение. Мы сначала докажем, что существует вектор [pic] такой, что

каждый корректный процесс получает N-1 компонентов [pic].

Случай 1: Все процессы нашли решение в A. Пусть [pic] будет вектором

достигнутых решений; каждый процесс получает N-1 компонентов [pic], хотя

"недостающий" компонент может быть различным для каждого процесса.

Случай 2: Все процессы за исключением одного, допустим r, нашли решение в

A. Все корректные процессы получают одни и те же N-1 решений, а именно

решения всех процессов за исключением r. Возможно, что r потерпел аварию,

но, так как возможно , что r просто очень медленный, он все же сможет

достичь решения, то есть, существует вектор [pic], который расширяет

решения, принятые на настоящий момент.

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

связном компоненте этого вектора.

Нетривиальность. Из нетривиальности A, можно достичь векторы решения как в

компоненте 0, так и в компоненте 1; по построению А’ оба решения возможны.

Таким образом, А' является асинхронным, детерминированным, 1-аварийно-

устойчивым алгоритмом согласия. Алгоритма А не существует по Теореме 13.8.

(

Обсуждение. Требование нетривиальности, утверждающее, что каждый вектор

решения в [pic] достижим, является довольно сильным. Можно спросить, могут

ли некоторые алгоритмы, которые являются тривиальными в этом смысле тем не

менее быть интересными. В качестве примера, рассмотрим Алгоритм 13.2 для

переименования; с ходу не видно, что он нетривиален, то есть, каждый вектор

с отдельным именем достижим (да, достижим); еще менее понятно то, почему

нетривиальность может представлять интерес в этом случае.

Исследование доказательства Теоремы 13.15 показывает, что в доказательстве

можно использовать более слабое требование нетривиальности, а именно, что

векторы решения достижимы по крайней мере в двух различных связных

компонентах [pic]. Такую ослабленную нетривиальность можно иногда вывести

из формулировки проблемы.

Фундаментальная работа о задачах решения, которые являются разрешимыми и

неразрешимыми при наличии одного сбойного процессора, была выполнена

Бираном, Мораном и Заксом [BMZ90]. Они дали полную комбинаторную

характеристику разрешимых задач решения.

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

В доказательстве Теоремы 13.8 показано, что каждый асинхронный алгоритм

согласия имеет бесконечные выполнения, в которых никакое решение не

принимается. К счастью, для хорошо подобранных алгоритмов такие выполнения

могут быть достаточно редки и иметь вероятность 0, что делает алгоритмы

очень полезными в вероятностном смысле; см. Главу 9. В этом разделе мы

представляем два вероятностных алгоритма согласия, один для модели аварий,

другой для Византийской модели; алгоритмы были предложены Брахой и Туэгом

[BT85]. В обоих случаях сначала доказывается верхний предел для способности

восстановления (t < N/2 и t < N/3, соответственно) и что и оба алгоритма

удовлетворяют соответствующей границе.

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

требование завершения сделано вероятностным, то есть, заменено более слабым

требованием сходимости.

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

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

Частичная правильность (Соглашение) должна удовлетворяться при каждом

выполнении; возникающие в результате вероятностные алгоритмы имеют класс

Las Vegas (Подраздел 9.1.2).

Вероятность принимается всеми выполнениями, начинающимися в данной

начальной конфигурации. Чтобы вероятности были значимыми, должно быть

задано распределение вероятности над этими выполнениями. Это можно сделать

использованием рандомизации в процессах (как в Главе 9), но здесь вместо

этого определяется распределение вероятности на прибытиях сообщений.

Распределение вероятности на выполнениях, начинающихся в данной начальной

конфигурации, определяется предположением о законном планировании. Оба

алгоритма функционируют в раундах; в раунде процесс “выкрикивает” сообщение

и ждет получения N-t сообщений. Определим R(q, p, k) как событие, когда в

раунде k процесс p получает (раунд-k) сообщение q среди первых N-t

сообщений. Законное планирование означает, что

[pic] [pic].

Для всех 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-аварийно-устойчивого протокола согласия для [pic]не

существует.

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

следующий три требования.

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

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

читателю. (

Для подмножества процессов S, конфигурация [pic] называется S-валентной,

если и 0- и 1-решенные конфигурации достижимы из [pic] с помощью только

шагов в S. [pic]называется S-0-валентной если, делая шаги только в S, 0-

решенная конфигурация, и никакая 1-решенная конфигурации, может быть

достигнута, S-1-валентная конфигурация определяется аналогично.

Разделим процессы на две группы, S и T, размера [pic] и [pic].

Требование 13.18 Достижимая конфигурация [pic]является или S-0-валентной и

T-0-валентной, или S-1-валентной и T-1-валентной.

Доказательство. Действительно, высокая способность восстановления протокола

подразумевает, что и S и T могут достигать решения независимо; если

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

объединяя планы. (

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

Доказательство. Пусть дана достижимая бивалентная конфигурация [pic] и

предположим, что это [pic] S-l-валентна и T-1-валентна (используем

Требование 13.18). Однако, [pic] бивалентна, поэтому (ясно из связи между

группами) 0-решенная конфигурация [pic] также достижима из [pic]. В

последовательности конфигураций от [pic]до [pic] имеются две последующих

конфигурации [pic] и [pic], где [pic] является и S-v-валентной и T-v-

валентной. Пусть p - процесс, вызывающий переход из [pic] в [pic]. Теперь

невыполнимо [pic], потому что [pic] S-1-валентна и [pic] S-0-валентна;

аналогично невыполнимо [pic]. Мы пришли к противоречию. (

Противоречие существованию протокола P является результатом Требований

13.17 и 13.19; таким образом Теорема 13.16 доказана. (

Аварийно-устойчивый алгоритм согласия Брахи и Туэга. Аварийно-устойчивый

алгоритм согласия, предложенный Брахой и Туэгом [BT85] функционирует в

раундах: в раунде k процесс посылает сообщение всем процессам (включая

себя) и ждет получения N-t сообщений раунда k. Ожидание такого числа

сообщений не представляет возможность тупика (см. Упражнение 13.10).

В каждом раунде, процесс p “выкрикивает” голос за 0 или за 1 вместе с

весом. Вес - число голосов, полученных для этого значения в предыдущем

раунде (1 в первом раунде); голос с весом, превышающим N/2, называется

свидетелем. Хотя различные процессы в раунде могут голосовать по-разному, в

одном раунде никогда нет свидетелей различных значений, как будет показано

ниже. Если процесс p получает свидетеля в раунде k, p голосует за свое

значение в раунде k+1; иначе p голосует за большинство полученных голосов.

Решение принимается, если в раунде получено больше, чем t свидетелей;

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