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

Перейти к навигации Перейти к поиску
Строка 60: Строка 60:
Начиная с 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> и <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>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. Но все процессы, кроме В, имеют одинаковые локальные состояния в конце каждого выполнения, поэтому они не могут принимать решения с разными значениями, что составляет противоречие.   




Источник — http://pco.iis.nsk.su/wega/index.php/Невозможность_асинхронного_консенсуса