Невозможность асинхронного консенсуса: различия между версиями

Рассмотрим распределенную систему, состоящую из множества ''процессов'', которые взаимодействуют между собой путем отправки и получения сообщений. Сеть представляет собой мультимножество сообщений, в котором каждое сообщение адресовано некоторому процессу. Процесс – это машина состояний, которая может выполнять три вида ''шагов''.

• На шаге ''отправки'' (send) процесс помещает сообщение в сеть.

• ''Согласованность'': значения решений всех процессов должны быть согласованными.

Без потери общности можно ограничиться ''бинарным'' консенсусом, у которого входные значения могут быть равны 0 или 1. ''Состояние протокола'' – это комплекс состояний процессов и мультимножества сообщений, проходящих по сети. ''Начальным состоянием'' является состояние протокола до того, как какой-либо процесс начал движение, а ''конечным'' – состояние протокола после завершения всех процессов. ''Значение решения'' в любом конечном состоянии представляет собой значение, принятое всеми процессами в этом состоянии.

Доказательство. Предположим от противного, что существует протокол консенсуса для (n + 1) потоков <math>A_0, ..., A_n</math>, в котором каждое начальное состояние является унивалентным. Обозначим за <math>s_i</math> начальное состояние, в котором процессы <math>A_i, ..., A_n</math> имеют на входе 0, а у <math>A_0, ..., A_{i - i}</math> на входе 1. Очевидно, что <math>s_0</math> является 0-валентным: все процессы имеют на входе 0, поэтому по условию допустимости все они должны прийти к решению 0. Если <math>s_i</math> является 0-валентным, то и <math>s_{i + 1}</math> тоже. Эти состояния отличаются только входными данными процесса <math>A_i</math>: 0 у <math>s_i</math> и 1 у <math>s_{i + 1}</math>. Любое выполнение, начинающееся с <math>s_i</math>, в котором <math>A_i</math> останавливается перед выполнением каких-либо шагов, неотличимо от выполнения, начинающегося с <math>s_{i + 1}</math>, в котором <math>A_i</math> останавливается перед выполнением каких-либо шагов. Поскольку в первом случае процессы должны принять решение 0, во втором они должны принять решение 1. А поскольку существует одно исполнение, начинающееся с <math>s_{i + 1}</math>, которое принимает решение 0, и поскольку согласно гипотезе <math>s_{i + 1}</math> унивалентно, то <math>s_{i + 1}</math> является 0-валентным. Отсюда следует, что состояние <math>s_{n + 1}</math>, в котором все процессы начинаются со входного значения 1, является 0-валентным, что противоречит условию. <math>\Box</math>

Доказательство от противного. Согласно лемме 1, протокол имеет бивалентное начальное состояние. Запустим выполнение протокола в этом состоянии. Многократно выбираем процесс, следующий шаг которого оставляет протокол в бивалентном состоянии, и позволяем данному процессу сделать этот шаг. Либо протокол будет работать вечно, нарушая условие завершения, либо в конце концов перейдет в критическое состояние. <math>\Box</math>

'''Теорема 3. Не существует протокола консенсуса для асинхронной системы передачи сообщений, в которой один процесс может претерпеть сбой.'''

Доказательство. Предположим от противного, что такой протокол существует. Будем выполнять протокол, пока он не достигнет критического состояния s. Должны существовать два процесса A и B, такие, что следующий шаг A переводит протокол в 0-валентное состояние, а следующий шаг B переводит его в 1-валентное состояние.

Начиная с s, обозначим за <math>s_A</math> состояние, достигаемое в случае, если A делает первый шаг, за <math>s_B</math> – если B делает первый шаг, за <math>s_{AB}</math> – если A делает шаг, за которым следует B, и так далее. Состояния <math>s_A</math> и <math>s_{AB}</math> являются 0-валентными, а <math>s_B</math> и <math>s_{BA}</math> – 1-валентными. Остается провести разбор случаев.

Из всех возможных пар шагов, которые A и B могли бы выполнить, большинство из них ''коммутативны'': состояния <math>s_{AB}</math> и <math>s_{BA}</math> идентичны, что порождает противоречие, поскольку они имеют разные валентности.

Единственная пара некоммутативных шагов имеет место в случае, когда А собирается отправить сообщение В (или наоборот). Обозначим за <math>s_{AB}</math> состояние, возникающее, если А посылает сообщение В, а В затем его получает, а за <math>s_{BA}</math> – состояние, возникающее, если В получает другое (или ''нулевое'') сообщение, а затем А посылает свое сообщение процессу В. Обратите внимание, что каждый процесс, отличный от В, имеет одно и то же локальное состояние в <math>s_{AB}</math> и <math>s_{BA}</math>. Рассмотрим выполнение, начинающееся с <math>s_{AB}</math>, в котором каждый процесс, кроме В, делает шаги в порядке очереди. Поскольку <math>s_{AB}</math> является 0-валентным, все эти процессы в конечном итоге найдут решение 0. Далее рассмотрим выполнение, начинающееся с <math>s_{BA}</math>, в котором каждый процесс, отличный от В, делает шаги в порядке очереди. Поскольку <math>s_{BA}</math> является 1-валентным, все эти процессы в конечном итоге найдут решение 1. Но все процессы, кроме В, имеют одинаковые локальные состояния в конце каждого выполнения, поэтому они не могут принимать решения с разными значениями, что составляет противоречие. <math>\Box</math>

Многие исследователи изучали альтернативные модели вычислений, в которых можно достичь консенсуса. Долев, Дворк и Стокмайер [5] рассматривают различные альтернативные модели передачи сообщений, определяя точные предположения, необходимые для возможности достижения консенсуса. Дворк, Линч и Стокмайер [6] вывели верхние и нижние границы для полусинхронной модели, в которой есть верхняя и нижняя границы времени доставки сообщений. Бен-Ор [1] показал, что введение рандомизации делает возможным консенсус в асинхронной системе передачи сообщений. Чандра и Туэг [3] продемонстрировали, что консенсус становится возможным при наличии оракула, способного (ненадежно) определить, когда процесс закончился сбоем. Каждая из процитированных здесь работ вдохновила множество последующих. Желающим разобраться в теме рекомендуем для начала прекрасный обзор Фич и Рупперта [7].

Протокол является ''протоколом без ожидания'', если он допускает сбои в работе всех участников, кроме одного. Параллельная реализация объектов ''линеаризуема'' в случае, если каждый вызов метода мгновенно производит эффект в какой-то момент между обращением к нему и его ответом. Херлихи [9] показал, что каждому объекту совместно используемой памяти можно присвоить ''номер консенсуса'' – максимальное количество процессов, для которых существует протокол консенсуса без ожидания, использующий комбинацию памяти с возможностью чтения/записи и рассматриваемых объектов. Номера консенсуса порождают бесконечную иерархию объектов, в которой (несколько упрощая) вышестоящие объекты являются более мощными по сравнению с нижестоящими. В системе из n или более параллельных процессов невозможно построить свободную от блокировок реализацию объекта с номером консенсуса n из объекта с меньшим номером консенсуса. С другой стороны, любой объект с номером консенсуса n является ''универсальным'' в системе из n или менее процессов: он может быть использован для построения линеаризуемой реализации любого объекта без ожидания.

В 1990 году Чаудхури [4] представила [[Согласование множеств|задачу о согласовании k множеств]] (k-set agreement problem), иногда называемую ''задачей о нахождении консенсуса для k множеств'', которая обобщает задачу достижения консенсуса, позволяя выбирать k или меньше различных значений решения. В частности, консенсусом является задача о согласовании для 1 множества. Вопрос о том, можно ли решить задачу о согласовании k множеств в асинхронных моделях передачи сообщений, оставался открытым в течение нескольких лет, пока три независимые группы исследователей [2, 10, 11] не доказали, что такого протокола не существует.