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