Теперь после отправления маркера θq > qtP0 продолжает сохраняться. Это означает, что подтверждение для сообщения, которое сделало q не quiet, послается r с временной пометкой θ0 > qtP0 . Таким образом, когда r стал quiet, после получения этого подтверждения, θr > qtP0 сохраняется, и следовательно qtr > qtP0 сохраняется, когда r получает маркер. Согласно алгоритму r не отправляет маркер; т.о. мы пришли к противоречию. -
Описание этого алгоритма, который не полагался на кольцевую топологию, было представлено Huang [Hua88].
Упражнение 8.1 Оаарактеризуйте активные и пассивные состояния Алгоритма А.2. Где эти состояния находятся в Алгоритме A.1?
Сложность по времени алгоритма обнаружения завершения определена как число единиц времени в худшем случае (согласно идиализационным предположениям Определения 6.31) между завершением основного вычисления и вызова алгоритмя объявления.
Упражнение 8.2. Что является сложностью по времени Dijkstra-Scholten алгоритма?
Упражнение 8.3. Shavit-Francez алгоритм применяется в произвольной сети с уникальными идентификаторами, и для того, чтобы минимизировать накладные расходы на управляющие сообщения Gallager-Humblet-Spira алгоритм используется как алгоритм волны. Сложность времени обнаружения - Ω(NlogN).
Можите ли вы улучшить сложность по времени до 0 (N) за счет обмена 0 (N) дополнительных управляющих сообщений?
Упражнение 8.4. Почему предикат P0в выводе алгоритма Dijkstra-Feijen-Van Gasteren, не принимает значение ложь, если pj активизирован pi, где j £ t или i > t?
Упражнение 8.5 Покажите, что для каждого m существует основное вычисление, которое использует m сообщений и заставляет алгоритм Dijkstra-Feijen-Van Gasteren использовать m(N - 1) управляющих сообщений.
Упражнение 8.6. Какие модификации должны быть сделаны в Алгоритме 8.9, чтобы осуществить правило 5a алгоритма восстановления кредита, вместо правила 5b?
Упражнение 8.7 В алгоритме Рана принято, что процессы имеют идентификаторы. Теперь примите вместо этого, что процессы анонимны, но имеют средства посылки сообщений их преемникам в кольце, и что число процессов известен. Измените Алгоритм 8.10, чтобы работать согласно этому предположению.
Упражнение 8.8 Покажите правильность алгоритма Рана (Алгоритм 8.10) из инварианта алгоритма.
13 Отказоустойчивость в Асинхронных Системах
Эта глава рассматривает разрешимость проблем решения в асинхронных распределенных системах. Результаты организованы вокруг фундаментального результата Фишера, Линча и Патерсона [FLP85], представленного в Разделе 13.1. Сформулированный как доказательство невозможности для класса алгоритмов решения, результат можно также трактовать как список предположений, которые совместно исключают разрешение проблем решения. Смягчение этих предположений позволяет получить практические решения различных проблем, как показано в последующих разделах. Дальнейшее обсуждение см. в Подразделе 13.1.3.
13.1 Невозможность согласия
В этом разделе доказывается фундаментальная теорема Фишера, Линча и Патерсона [FLP85] об отсутствии асинхронных, детерминированных 1-аварийно устойчивых протоколов согласия. Результат показан рассуждением, включающим в себя законные последовательности выполнения алгоритмов. Сначала введем обозначения (вдобавок к введенным в Разделе 2.1) и укажем элементарные результаты, которые окажутся полезными далее.
13.1.1 Обозначения, Определения, Элементарные Результаты
Последовательность событий применима в конфигурации , если применима в , - в , и т.д. Если - результирующая конфигурация, то, чтобы явно указать события, ведущие от к , мы пишем или . Если и содержит только события в процессах из , мы также пишем .
Утверждение 13.1 Пусть последовательности и применимы в конфигурации , и пусть ни один процесс не участвует одновременно в и , тогда применима в , применима в , и .
Доказательство. Следует из повторного применения Теоремы 2.19. -
Процесс имеет входную переменную , доступную только для чтения, и выходной регистр однократной записи с начальным значением . Входная конфигурация полностью определяется значением для каждого процесса . Процесс может принять решение о значении (обычно 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-аварийное законное, и процессы в корректны; следовательно они достигают решения -
Лемма 13.5 Достижимой развилки не существует.
Доказательство. Пусть - достижимая конфигурация и - подмножество самое большее из процессов.
Пусть будет дополнением , т.е., . В по меньшей мере N-t процессов, следовательно существует решенная конфигурация такая, что (Утверждение 13.4). Конфигурация либо 0-, либо 1-решенная; положим, что она 0-решенная.
Сейчас будет показано, что ни для какой 1-валентной ; пусть - любая такая конфигурация, что . Так как шаги в и заменяются (Утверждение 13.1), есть конфигурация , которая достижима и из , и из. Так как - 0-решенна, то и- тоже, что показывает не 1-валентность . -
13.1.2 Доказательство невозможности
Сначала, используя нетривиальность проблемы, покажем что существует бивалентная начальная конфигурация (Лемма 13.6). Вполедствии будет показано, что начиная с бивалентной конфигурации, каждый доступный шаг можно исполнять без перехода в унивалентную конфигурацию (Лемма 13.7). Этого достаточно, чтобы показать невозможность алгоритмов согласия (Теорема 13.8). В дальнейшем, пусть А - 1-аварийно-устойчивый алгоритм согласия.
Лемма 13.6 Для А существует бивалентная начальная конфигурация.
Доказательство. Так как А нетривиален (Определение 13.3), то есть достижимые 0- и 1-решенные конфигурации; пусть и - начальные конфигурации такие, что -решенная конфигурация достижима из .
Если , эта начальная конфигурация бивалентна и результат имеет силу. Иначе, есть начальные конфигурации и такие, что -решенная конфигурация достижима из , и и различаются входом одного процесса. Действительно, рассмотрим последовательность начальных конфигураций, начинающуюся с и заканчивающуюся , в которой каждая следующая начальная конфигурация отличается от предыдущей в одном процессе. (Эта последовательность получается инвертированием входных битов одного за другим.) Из первой конфигурации в последовательности, , достижима 0-решенная конфигурация, и из последней, , достижима 1-решенная конфигурация. Так как решенная конфигурация достижима из каждой начальной конфигурации, описанные и можно найти в последовательности. Пусть - процесс, в котором и различны.