292
правки
Изменения
→Начальная бивалентная конфигурация
=== Начальная бивалентная конфигурация ===
Лемма: существует бивалентная начальная конфигурация.
Доказательство от противного: пусть все начальные конфигурации одновалентны.
Из нетривиальности консенсуса мы знаем, что есть как 0-, так и 1-валентные начальные конфигурации.
Тогда можно найти две начальные конфигурации разной валентности, которые отличаются только состоянием одного процесса:
взяли две произвольные начальные конфигурации разной валентности, начали переводить одну в другую копированием исходных состояний процессов, по одному процессу за шаг.
А раз есть две такие конфигурации разной валентности, то пусть в каждой из них этот процесс (где они отличаются) откажет с самого начала, до отправки и приёма любых сообщений.
Тогда мы всё ещё получим консенсус, но решение будет одинаковым, потому что внешняя система никак не может выявить состояние отказавшего процесса.
А они исходно были разной валентности, противоречие.
=== Цепочка бивалентных конфигураций ===
