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

Доказательство. Предположим от противного, что существует протокол консенсуса для (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-валентным, что противоречит условию.