292
правки
Изменения
→Валентность
=== Валентность ===
Заметим, что в любом исполнении всегда принимается решение.
Даже если один процесс отказал, то все остальные должны прийти к решению за конечное число шагов.
{{Определение
|definition=
Конфигурация называется '''$i$-валентной''', если все цепочки шагов из неё приводят к решению $i$.
Таким образом, бывают 0-валентные и 1-валентные конфигурации.
Если же из конфигурации есть цепочки, приводящие к каждому из решений, то такая конфигурация называется '''бивалентной'''.
}}
Наблюдение: пусть из конфигурации $X$ есть цепочка шагов, обрабатывающая сообщения из $X$ в подмножестве процессов $A$, за которой идёт цепочка процессов, обрабатывающая сообщения из $X$ в подмножестве процессов $B$, и в конце мы получили конфигурацию $Y$. Тогда эти цепочки коммутируют: можно сначала обработать сообщения подмножеством процессов $B$, а потом — $A$ (так как мы обрабатываем только сообщения из $X$, а не новые).
=== Начальная бивалентная конфигурация ===
