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

Перейти к навигации Перейти к поиску
м
Строка 46: Строка 46:
'''Лемма 1'''. Каждый протокол консенсуса имеет бивалентное начальное состояние.
'''Лемма 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 у si+1. Любое выполнение, начинающееся с <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-валентным, что противоречит условию.
Доказательство. Предположим от противного, что существует протокол консенсуса для (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 у si+1. Любое выполнение, начинающееся с <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-валентным, что противоречит условию.




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


Доказательство. Предположим от противного, что такой протокол существует. Будем выполнять протокол, пока он не достигнет критического состояния. Должны существовать два процесса A и B, такие, что следующий шаг A переводит протокол в 0-валентное состояние, а следующий шаг B переводит протокол в 1-валентное состояние.
Доказательство. Предположим от противного, что такой протокол существует. Будем выполнять протокол, пока он не достигнет критического состояния 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-валентными. Остается провести разбор случаев.
Начиная с 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> и SBA идентичны, что порождает противоречие, поскольку они имеют разные валентности.
Из всех возможных пар шагов, которые A и B могли бы выполнить, большинство из них ''коммутируют'': состояния <math>s_{AB}</math> и SBA идентичны, что порождает противоречие, поскольку они имеют разные валентности.
4431

правка

Навигация