Быстрый поиск

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

Лемма 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-аварийно-устойчивого алгоритма согласия не существует.

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