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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «== Ключевые слова и синонимы == Консенсус без ожидания; согласование == Постановка задачи == Рассмотрим распределенную систему, состоящую из множества процессов, которые взаимодействуют между собой путем отправки и получения сообщений. Сеть представляе...»)
 
Нет описания правки
Строка 3: Строка 3:


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


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


• На шаге получения (receive) процесс A либо считывает и удаляет из сети сообщение, адресованное A, либо считывает выделенное нулевое значение, оставляя сеть без изменений. Если сообщение, адресованное A, помещено в сеть, и если A последовательно выполнит бесконечное число шагов получения, то в конце концов получит это сообщение.
• На шаге ''получения'' (receive) процесс A либо считывает и удаляет из сети сообщение, адресованное A, либо считывает выделенное ''нулевое'' значение, оставляя сеть без изменений. Если сообщение, адресованное A, помещено в сеть, и если A последовательно выполнит бесконечное число шагов получения, то в конце концов получит это сообщение.


• В состоянии вычисления (computation) процесс изменяет свое состояние без коммуникаций с каким-либо другим процессом.
• В состоянии ''вычисления'' (computation) процесс изменяет свое состояние без коммуникаций с каким-либо другим процессом.




Процессы являются асинхронными: не существует ограничений на их относительную скорость. Процессы могут претерпевать сбои: они могут просто остановиться и больше не делать никаких шагов. Далее рассматривается выполнение, в ходе которого сбой происходит не более чем у одного процесса.
Процессы являются ''асинхронными'': не существует ограничений на их относительную скорость. Процессы могут претерпевать ''сбои'': они могут просто остановиться и больше не делать никаких шагов. Далее рассматривается выполнение, в ходе которого сбой происходит не более чем у одного процесса.




В задаче о достижении консенсуса каждый процесс начинает работу с частного входного значения, общается с остальными, а затем останавливается со значением решения. Такие значения должны удовлетворять следующим свойствам:
В ''задаче о достижении консенсуса'' каждый процесс начинает работу с частного ''входного'' значения, общается с остальными, а затем останавливается со значением ''решения''. Такие значения должны удовлетворять следующим свойствам:


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


• Допустимость: каждое значение решения должно быть некоторым значением процесса.
''Допустимость'': каждое значение решения должно быть некоторым значением процесса.


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




Строка 27: Строка 27:


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




Строка 33: Строка 33:




Бивалентное состояние протокола – это состояние, в котором конечное значение решения еще не фиксировано. Из любого бивалентного состояния существует выполнение, в котором конечное значение решения равно 0, и другое, в котором оно равно 1. Унивалентное состояние протокола – это состояние, в котором исход фиксирован. Каждое выполнение, начиная с унивалентного состояния, находит решение с одним и тем же значением. 1-валентное состояние протокола является унивалентным с конечным значением решения 1; аналогично для 0-валентного состояния.
''Бивалентное'' состояние протокола – это состояние, в котором конечное значение решения еще не фиксировано. Из любого бивалентного состояния существует выполнение, в котором конечное значение решения равно 0, и другое, в котором оно равно 1. ''Унивалентное'' состояние протокола – это состояние, в котором исход фиксирован. Каждое выполнение, начиная с унивалентного состояния, находит решение с одним и тем же значением. ''1-валентное'' состояние протокола является унивалентным с конечным значением решения 1; аналогично для ''0-валентного'' состояния.




Состояние протокола является критическим, если:
Состояние протокола является ''критическим'', если:


• оно бивалентно и
• оно бивалентно и
Строка 44: Строка 44:
== Основные результаты ==
== Основные результаты ==


Лемма 1. Каждый протокол консенсуса имеет бивалентное начальное состояние.
'''Лемма 1'''. Каждый протокол консенсуса имеет бивалентное начальное состояние.


Доказательство. Предположим от противного, что существует протокол консенсуса для (n + 1) потоков A0, …, An, в котором каждое начальное состояние является унивалентным. Обозначим за si начальное состояние, в котором процессы A,-,--- ;An имеют на входе 0, а A0 ... ; Aj-i – 1. Очевидно, что S0 является 0-валентным: все процессы имеют на входе 0, поэтому по условию допустимости все они должны прийти к решению 0. Если si является 0-валентным, то и si+1 тоже. Эти состояния отличаются только входными данными процесса Ai: 0 у si и 1 – у si+1. Любое выполнение, начинающееся с si, в котором Ai останавливается перед выполнением каких-либо шагов, неотличимо от выполнения, начинающегося с si+1, в котором Ai останавливается перед выполнением каких-либо шагов. Поскольку в первом случае процессы должны принять решение 0, во втором они должны принять решение 1. А поскольку существует одно исполнение, начинающееся с si+1, которое принимает решение 0, и поскольку согласно гипотезе si+1 унивалентно, то si+1 является 0-валентным. Отсюда следует, что состояние sn+1, в котором все процессы начинаются со входного значения 1, является 0-валентным, что противоречит условию.
Доказательство. Предположим от противного, что существует протокол консенсуса для (n + 1) потоков A0, …, An, в котором каждое начальное состояние является унивалентным. Обозначим за si начальное состояние, в котором процессы A,-,--- ;An имеют на входе 0, а A0 ... ; Aj-i – 1. Очевидно, что S0 является 0-валентным: все процессы имеют на входе 0, поэтому по условию допустимости все они должны прийти к решению 0. Если si является 0-валентным, то и si+1 тоже. Эти состояния отличаются только входными данными процесса Ai: 0 у si и 1 – у si+1. Любое выполнение, начинающееся с si, в котором Ai останавливается перед выполнением каких-либо шагов, неотличимо от выполнения, начинающегося с si+1, в котором Ai останавливается перед выполнением каких-либо шагов. Поскольку в первом случае процессы должны принять решение 0, во втором они должны принять решение 1. А поскольку существует одно исполнение, начинающееся с si+1, которое принимает решение 0, и поскольку согласно гипотезе si+1 унивалентно, то si+1 является 0-валентным. Отсюда следует, что состояние sn+1, в котором все процессы начинаются со входного значения 1, является 0-валентным, что противоречит условию.




Лемма 2. Каждый протокол консенсуса имеет критическое состояние.
'''Лемма 2'''. Каждый протокол консенсуса имеет критическое состояние.


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




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



Версия от 17:53, 27 апреля 2024

Ключевые слова и синонимы

Консенсус без ожидания; согласование

Постановка задачи

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

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

• На шаге получения (receive) процесс A либо считывает и удаляет из сети сообщение, адресованное A, либо считывает выделенное нулевое значение, оставляя сеть без изменений. Если сообщение, адресованное A, помещено в сеть, и если A последовательно выполнит бесконечное число шагов получения, то в конце концов получит это сообщение.

• В состоянии вычисления (computation) процесс изменяет свое состояние без коммуникаций с каким-либо другим процессом.


Процессы являются асинхронными: не существует ограничений на их относительную скорость. Процессы могут претерпевать сбои: они могут просто остановиться и больше не делать никаких шагов. Далее рассматривается выполнение, в ходе которого сбой происходит не более чем у одного процесса.


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

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

Допустимость: каждое значение решения должно быть некоторым значением процесса.

Завершение: каждый процесс без сбоев должен принять решение за конечное число шагов.


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

Терминология

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


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


Бивалентное состояние протокола – это состояние, в котором конечное значение решения еще не фиксировано. Из любого бивалентного состояния существует выполнение, в котором конечное значение решения равно 0, и другое, в котором оно равно 1. Унивалентное состояние протокола – это состояние, в котором исход фиксирован. Каждое выполнение, начиная с унивалентного состояния, находит решение с одним и тем же значением. 1-валентное состояние протокола является унивалентным с конечным значением решения 1; аналогично для 0-валентного состояния.


Состояние протокола является критическим, если:

• оно бивалентно и

• если какой-либо процесс совершает шаг, состояние протокола становится унивалентным.

Основные результаты

Лемма 1. Каждый протокол консенсуса имеет бивалентное начальное состояние.

Доказательство. Предположим от противного, что существует протокол консенсуса для (n + 1) потоков A0, …, An, в котором каждое начальное состояние является унивалентным. Обозначим за si начальное состояние, в котором процессы A,-,--- ;An имеют на входе 0, а A0 ... ; Aj-i – 1. Очевидно, что S0 является 0-валентным: все процессы имеют на входе 0, поэтому по условию допустимости все они должны прийти к решению 0. Если si является 0-валентным, то и si+1 тоже. Эти состояния отличаются только входными данными процесса Ai: 0 у si и 1 – у si+1. Любое выполнение, начинающееся с si, в котором Ai останавливается перед выполнением каких-либо шагов, неотличимо от выполнения, начинающегося с si+1, в котором Ai останавливается перед выполнением каких-либо шагов. Поскольку в первом случае процессы должны принять решение 0, во втором они должны принять решение 1. А поскольку существует одно исполнение, начинающееся с si+1, которое принимает решение 0, и поскольку согласно гипотезе si+1 унивалентно, то si+1 является 0-валентным. Отсюда следует, что состояние sn+1, в котором все процессы начинаются со входного значения 1, является 0-валентным, что противоречит условию.


Лемма 2. Каждый протокол консенсуса имеет критическое состояние.

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


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

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


Начиная с s, обозначим за SA состояние, достигаемое в случае, если A делает первый шаг, за SB – если B делает первый шаг, SAB – если A делает шаг, за которым следует B, и так далее. Состояния SA и SAB являются 0-валентными, а SB и SBA – 1-валентными. Остается провести разбор случаев.


Из всех возможных пар шагов, которые A и B могли бы выполнить, большинство из них коммутируют: состояния SAB и SBA идентичны, что порождает противоречие, поскольку они имеют разные валентности.


Единственная пара шагов, которые не коммутируют, имеет место тогда, когда А собирается отправить сообщение В (или наоборот). Обозначим за SAB состояние, возникающее, если А посылает сообщение В, а В затем его получает, а за SBA – состояние, возникающее, если В получает другое (или нулевое) сообщение, а затем А посылает свое сообщение В. Обратите внимание, что каждый процесс, отличный от В, имеет одно и то же локальное состояние в SAB и SBA. Рассмотрим выполнение, начинающееся с SAB, в котором каждый процесс, кроме В, делает шаги в порядке очереди. Поскольку SAB является 0-валентным, в конечном итоге будет найдено решение 0. Далее рассмотрим выполнение, начинающееся с SBA, в котором каждый процесс, отличный от В, делает шаги в порядке очереди. Поскольку SBA является 1-валентным, в конечном итоге будет найдено решение 1. Но все процессы, кроме В, имеют одинаковые локальные состояния в конце каждого выполнения, поэтому они не могут принимать решения с разными значениями, что составляет противоречие.


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

Применение

Задача о достижении консенсуса является ключевым инструментом для понимания возможностей различных асинхронных моделей вычислений.

Открытые вопросы

Существует множество открытых вопросов, касающихся разрешимости задачи о нахождении консенсуса в других моделях или при ограничениях на входные данные.

Родственные работы

Изначальная статья Фишера, Линч и Патерсона [8] до сих пор является образцом ясности.


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


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


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

См. также

Литература

1. Ben-Or, M.: Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In: PODC '83: Proceedings of the second annual ACM symposium on Principles of distributed computing, pp. 27-30. ACM Press, New York (1983)

2. Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the 1993 ACM Symposium on Theory of Computing, May 1993. pp. 206-215

3. Chandra, T.D.,Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225-267 (1996)

4. Chaudhuri, S.: Agreement is harder than consensus: Set consensus problems in totally asynchronous systems. In: Proceedings Of The Ninth Annual ACM Symposium On Principles of Distributed Computing, August 1990. pp. 311-234

5. Chandhuri, S.: More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems. Inf. Comput. 105(1), 132-158, July 1993

6. Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288-323 (1988)

7. Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distrib. Comput. 16(2-3), 121-163(2003)

8. Fischer, M., Lynch, N., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374-382 (1985)

9. Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. (TOPLAS) 13(1), 124-149 (1991)

10. Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858-923 (1999)

11. Saks, M.E., Zaharoglou, F.: Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput. 29(5),1449-1483(2000)