4501
правка
Невозможность асинхронного консенсуса: различия между версиями
Перейти к навигации
Перейти к поиску
Невозможность асинхронного консенсуса (посмотреть исходный код)
Версия от 17:53, 27 апреля 2024
, 27 апрельнет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Консенсус без ожидания; согласование == Постановка задачи == Рассмотрим распределенную систему, состоящую из множества процессов, которые взаимодействуют между собой путем отправки и получения сообщений. Сеть представляе...») |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 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-валентное состояние. | ||