Реферат: Распределенные алгоритмы
Утверждение 13.1
Пусть последовательности
и 
применимы в конфигурации 
, и пусть ни один процесс не
участвует одновременно в 
и 
, тогда 
применима в 
, 
применима в 
, и 
.
Доказательство. Следует из повторного применения Теоремы 2.19. o
Процесс 
имеет входную
переменную 
, доступную только для
чтения, и выходной регистр однократной записи 
с
начальным значением 
. Входная
конфигурация полностью определяется значением 
для
каждого процесса 
. Процесс 
может принять решение
о значении (обычно 1 или 0) записью его в 
;
начальное значение 
не является
значением решения. Предполагается, что корректный процесс исполняет бесконечно
много событий при законном выполнении; в крайнем
случае, процесс всегда может выполнять (возможно пустое) внутреннее событие.
Определение 13.2 t-аварийное законное выполнение - выполнение, в котором по меньшей мере N-t процессов исполняют бесконечно много событий, и каждое сообщение, посылаемое корректному процессу, получается. (Процесс корректен, если исполняет бесконечно много событий.)
Максимальное число сбойных процессов, с которым может справиться
алгоритм, называется способностью восстановления алгоритма, и всегда
обозначается 
. В этом разделе
демонстрируется невозможность существования асинхронного, детерминированного
алгоритма со способностью восстановления 1.
Определение 13.3 1-аварийно-устойчивый алгоритм согласия - алгоритм, удовлетворяющий следующим трем требованиям.
(1) Завершение. В каждом 1-аварийном законном исполнении, все корректные процессы принимают решение.
(2)
Согласованность. Если в достижимой конфигурации 
и 
для корректных процессов 
и 
, то 
.
(3)
Нетривиальность. Для 
и
для 
существуют достижимые
конфигурации, в которых для некоторого 
.
Для 
конфигурация
называется 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-аварийно-устойчивый алгоритм согласия.
Страницы: 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, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105
