292
правки
Изменения
→Цепочка бивалентных конфигураций
=== Цепочка бивалентных конфигураций ===
'''Лемма''': для любой бивалентной конфигурации можно найти следующую за ней бивалентную.
'''Следствие''': если лемма верна, то мы можем построить бесконечную цепочку бивалентных конфигураций и тем самым получим противоречие и докажем FLP: есть бесконечная цепочка, в которой не принято решение.
'''Доказательство''': от противного.
Пусть все конфигурации после некотороый бивалентной конфигурации $G$ одновалентны.
Введём определения:
* $e$ — какое-то событие в $G$, скармливающее сообщение $m$ процессу $p$. Такое есть, иначе у нас в конфигурации ничего не происходит, она бивалентна, а решение должно быть детерминированным, противоречие.
* $C$ — множество конфигураций, достижимых из $G$ без использования $e$. В частности, в $C$ по предположению отсутствуют бивалентные конфигурации.
* $D=e(C)$, то есть все конфигурации, достижимые из $G$, где $e$ — последнее обработанное событие. В частности, в $D$ по предположению отсутствуют бивалентные конфигурации.
Теперь докажем, что $D$ содержит бивалентную конфигурацию.
То есть мы выбрали, насколько сильно отложить обработку произвольного события $e$ и показали, что это не порушит бивалентность.
Надо ещё аккуратно, чтобы это не порушило конечность обработки каждого сообщения.
Например, их можно обрабатывать по очереди, начиная с самых старых.
Тогда каждое событие рано или поздно попадёт в наш шаг и будет обработано.
==== Шаг 1: существование $i$-валентных конфигураций в $D$ ====
'''Подлемма''': для любого $i$ в $D$ существует $i$-валентная конфигурация.
В самом деле: так как $G$ бивалентна, то по какой-то цепочке шагов из неё можно дойти до $i$-валентной конфигурации $E_i$.
Дальше разбором случаев находим искомую конфигурацию в $D$:
* Если $E_i \in D$, то мы доказали подлемму.
* Если $E_i \in C$, то $e(E_i) \in D$, у $e(E_i)$ такая же валентность и мы снова доказали подлемму.
* Иначе ребро $e$ применялось в цепочке шагов для достижения $E_i$ из $G$. Найдём конфигурацию $F_i \in D$, которая была в этой цепочке шагов сразу после применения $e$. Так как в $D$ нет бивалентных конфигураций, то $F_i$ является $i$-валентной, что и требовалось.
==== Шаг 2: существование соседних разновалентных конфигураций ====
==== Шаг 3: разбор случаев ====
== Ссылки ==
* http://bailonga.es/tpmtp/lecture09.pdf
* https://github.com/volhovm/study-notes/blob/master/parallel_programming/parallel_programming.org
