Рассмотрим законное выполнение, начинающееся с , в которой не делает шагов; это выполнение 1-аварийно законное и следовательно достигает решенной конфигурации . Если 1-решенная, бивалентна. Если 0-решенная, заметьте, что отличается от только в , а не делает шагов в выполнении; следовательно достижима из , что показывает бивалентность . (Более точно, конфигурация достижима из , где отличается от только в состоянии ; следовательно 0-решенная.) -
Чтобы поñòðîèòь законное выполнение без принятия решения мы должны показать, что каждый процесс может сделать шаг, и что каждое сообщение может быть получено не обуславливая принятие решения. Пусть шаг s обозначает получение и обработку отдельного сообщения или спонтанное действие (внутреннее или посылки) отдельного процесса. Состояние процесса, делающего шаг, может привести к различным событиям. Прием сообщения применим, если оно в пути, и спонтанный шаг всегда применим.
Лемма 13.7 Пусть - достижимая бивалентная конфигурация и s - применимый шаг для процесса p в . Существует последовательность событий такая, что s применим в , и бивалентна.
Доказательство. Пусть С - множество конфигураций, достижимых из без применения s, т.е., С = {: s не происходит в }; s применим в каждой конфигурации С (напомним, что s - шаг, а не отдельное событие).
В С есть конфигурации и такие, что из достижима v-решенная конфигурация. Чтобы убедится в этом, заметим, что, т.к. бивалентна, из нее достижимы v-решенные конфигурации для v =0,1. Если (т.е. для достижения решенной конфигурации s не применялся), заметим, что , тем не менее, v-решенная, поэтому выберем . Если (т.е. для достижения решенной конфигурации s применялся), выберем как конфигурацию, из которой применялся s.
Если , - искомая бивалентная конфигурация. Предположим, что , и рассмотрим конфигурации на путях от до и . Две конфигурации на этих путях называются соседними, если одна получается из другой за один шаг. Так как 0-решенная конфигурация достижимаа из и 1-решенная конфигурация достижима из , то
(1) на путях есть конфигурация такая, что бивалентна; или
(2) есть соседи и такие, что 0-валентна и - 1-валентна.
В первом случае - искомая бивалентная конфигурация и лемма доказана. Во втором случае, одна конфигурация из и - развилкой, что является противоречием. Действительно, предположим, что получена за один шаг из , т.е., для события e в процессе q. Теперь - это и, следовательно, 1-валентна, но не 1-валентна, т.к. уже 0-валентна. Итак, е и s не заменяются, что подразумевает (Теорема 2.19) , что p = q, но тогда достижимая конфигурация удовлетворяет и . Так как первая 0-валентна, а последняя 1-валенттна, - развилка, что является противоречием. -
Теорема 13.8 Асинхронного, детерминированного, 1-аварийно-устойчивого алгоритма согласия не существует.
Доказательство. Если предположить, что такой алгоритм существует, можно построить законное выполнение без принятия решения, начиная с бивалентной начальной конфигурации .
Когда построение дойдет до конфигурации , выберем в качестве применимый шаг, который был применим самое большое число раз. По предыдущей лемме, выполнение можно расширить так, что исполняется и достигается бивалентная конфигурация .
Такое построение дает бесконечное законное выполнение, в котором все процессы корректны, но решение никогда не будет принято. -
13.1.3 Обсуждение
Вывод утверждает, что не существует асинхронных, детерминированных, 1-аварийно-устойчивых алгоритмов решения для проблемы согласия; это исключает алгоритмы для класса нетривиальных проблем. (см. Подраздел 12.2.2).
К счастью, некоторые предположения, лежащие в основе результата Фишера, Линча и Патерсона, можно выразить явно, и результат, как оказывается, очеть чувствителен к ослаблению любого из них. Несмотря на вывод о невозможности, многие нетривиальные проблемы имеют решения, даже в асинхронных системах и где процессы могут отказывать.
(1) Ослабленная модель отказов. Раздел 13.2 рассматривает модель отказов изначально-мертвых процессов, которая слабее, чем модель аварий, и в этой модели согласие и выборы детерминированно достижимы.
(2) Ослабленная координация. Раздел 13.3 рассматривает проблемы, которые требуют менее тесной координации между процессами, чем согласие, и показывает, что некоторые из этих проблем, включая переименование, разрешимы в модели аварий.
(3) Рандомизация. Раздел 13.4 рассматривает протоколы с уравненными вероятностями, где требование завершения достаточно ослаблено, чтобы обеспечить решения даже при присутствии Византийских отказов.
(4) Слабое требование завершения. Раздел 13.5 рассматривает другое ослабление требования завершения, а именно где разрешение требуется только когда данный процесс корректен; здесь также возможны Византийско-устойчивые решения.
(5) Синхронность. Влияние синхронности изучается далее в Главе 14.
Возможны довольно тривиальные решения, если одно из трех требований Определения 13.3 просто опущено; см. Упражнение 13.1. Исключение предположения (неявно использованного в доказательстве Леммы 13.6) о том, что возможны все комбинации входов, изучается в Упражнении 13.2.
13.2 Изначально-мертвые Процессы
В модели изначально-мертвых процессов, ни один процесс не может отказать после исполнения события, следовательно, при законном выполнении каждый процесс исполняет либо 0, либо бесконечно много событий.
Определение 13.9 t-изначально-мертвых законное выполнение - выполнение, в котором по крайней мере N-t процессов активны, каждый активный процесс исполняет бесконечно много событий, и каждое сообщение, посылаемое корректному процессу, принимается.
В t-изначально-мертвых-устойчивом алгоритме согласия, каждый корректный процесс принимает решение в каждом t-изначально-мертвых законном выполнении. Согласованность и нетривиальность определяются так же, как в модели аварий.
var , , : sets of processes init 0;
begin shour <name, >;
(* т.е.: 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] рассмотрели проблему для клик с чувством направления и предложили алгоритм сообщений, который также является оптимальным.