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

Для  конфигурация называется v-решенной, если для некоторого  ; конфигурация называется решенной, если она 0-решенная или 1-решенная. В -решенной конфигурации какой-нибудь процесс принял решение . Конфигурация называется v-валентной, если все решенные конфигурации, достижимые из нее, v-решенны. Конфигурация называется бивалентной, если из нее достижимы как 0-валентные, так и  1-валентные конфигурации, и унивалентной, если она либо 1-валентная, либо 0-валентная. В унивалентной конфигурации, хотя никакое решение не было обязательно принято никаким процессом, окончательное решение уже неявно определено.

Конфигурация  -устойчивого протокола называется развилкой, если существует множество  (самое большее) из  процессов и конфигурации  и  такие, что , , и  -валентна. Неформально, - развилка, если подмножество из  процессов может добиться 0-решенности так же, как и 1-решенности. Следующее утверждение формально фиксирует, что в любой момент оставшиеся процессы должна вынести аварию самое большее  процессов.

Утверждение 13.4 Для каждой достижимой конфигурации t-устойчивого алгоритма и каждого подмножества S по меньшей мере из N-t процессов существует решенная конфигурация  такая, что .

Доказательство. Пусть   и  удовлетворяют условию и рассмотрим выполнение, которое достигает конфигурации  и содержит бесконечно много событий в каждом процессе из  впоследствии (и никаких шагов процессов не из ). Это выполнение - t-аварийное законное, и процессы в  корректны; следовательно они достигают решения                                                                                       o

Лемма 13.5 Достижимой развилки не существует.

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

Пусть  будет дополнением , т.е., . В  по меньшей мере N-t  процессов, следовательно существует решенная конфигурация  такая, что  (Утверждение 13.4). Конфигурация  либо 0-, либо 1-решенная; положим, что она 0-решенная.

Сейчас будет показано, что  ни для какой 1-валентной ; пусть  - любая такая конфигурация, что . Так как шаги в  и  заменяются (Утверждение 13.1), есть конфигурация , которая достижима и из , и из. Так как  - 0-решенна, то и- тоже, что показывает не 1-валентность .     o

13.1.2 Доказательство невозможности

Сначала, используя нетривиальность проблемы, покажем что существует бивалентная начальная конфигурация (Лемма 13.6). Вполедствии будет показано, что начиная с бивалентной конфигурации, каждый доступный шаг можно исполнять без перехода в унивалентную конфигурацию (Лемма 13.7). Этого достаточно, чтобы показать невозможность алгоритмов согласия (Теорема 13.8). В дальнейшем, пусть А - 1-аварийно-устойчивый алгоритм согласия.

Лемма 13.6 Для А существует бивалентная начальная конфигурация.

Доказательство. Так как А нетривиален (Определение 13.3), то есть достижимые 0- и 1-решенные конфигурации; пусть  и  - начальные конфигурации такие, что -решенная конфигурация достижима из .

Если , эта начальная конфигурация бивалентна и результат имеет силу. Иначе, есть начальные конфигурации  и  такие, что -решенная конфигурация достижима из , и  и  различаются входом одного процесса. Действительно, рассмотрим последовательность начальных конфигураций, начинающуюся с  и заканчивающуюся , в которой каждая следующая начальная конфигурация отличается от предыдущей в одном процессе. (Эта последовательность получается инвертированием входных битов одного за другим.) Из первой конфигурации в последовательности, , достижима 0-решенная конфигурация, и из последней, , достижима 1-решенная конфигурация. Так как решенная конфигурация достижима из каждой начальной конфигурации, описанные  и  можно найти в последовательности. Пусть  - процесс, в котором  и  различны.

Рассмотрим законное выполнение, начинающееся с , в которой  не делает шагов; это выполнение 1-аварийно законное и следовательно достигает решенной конфигурации . Если  1-решенная,  бивалентна. Если  0-решенная, заметьте, что  отличается от  только в , а  не делает шагов в выполнении; следовательно  достижима из , что показывает бивалентность . (Более точно, конфигурация  достижима из , где  отличается от  только в состоянии ; следовательно  0-решенная.)   o

Чтобы поñòðîèòь законное выполнение без принятия решения мы должны показать, что каждый процесс может сделать шаг, и что каждое сообщение может быть получено не обуславливая принятие решения. Пусть шаг 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-валенттна,  - развилка, что является противоречием.                                                                                                                               o

Теорема 13.8 Асинхронного, детерминированного, 1-аварийно-устойчивого алгоритма согласия не существует.

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

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

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

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, >.

Изначально-мертвый процесс не получал и не посылал никаких сообщений, следовательно он формирует изолированную вершину в ; у корректного процесса есть  преемников, следовательно, он не изолирован. Узел - это сильносвязный компонент без исходящих дуг, содержащий по меньшей мере две вершины. В  есть узел, содержащий корректные процессы, и, так как каждый корректный процесс имеет степень выхода , этот узел имеет размер по меньшей мере . В результате, так как , существует ровно один узел; назовем его . В конечном счете, так как корректный процесс  имеет  преемников, по меньшей мере один из них принадлежит , что означает, что все процессы в  - потомки .

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