distributed-computing - FLP 不可能结果证明中存在 0 价和 1 价配置

Question

在已知论文Impossibility of Distributed Consensus with one Faulty Process (JACM85) ，FLP(Fisher、Lynch 和 Paterson)证明了一个令人惊讶的结果，即没有完全异步的共识协议(protocol)可以容忍甚至一个未通知的进程死亡。

在引理 3 中，在证明 D 包含 0 价和 1 价配置后，它说:

Call two configurations neighbors if one results from the other in a single step. By an easy induction, there exist neighbors C₀, C₁ ∈ C such that Dᵢ = e(Cᵢ) is i-valent, i = 0, 1.

我可以遵循整个证明，除非他们声称存在这样的 C₀ 和 C₁。你能给我一些提示吗？

Answer 1

D (将 e 应用于 C 的元素后的可能配置集)包含 0 价和 1 价配置(并且假定不包含二价配置)。

即——e映射 C 中的每个元素为 0 价或 1 价配置。根据 C 的定义，必须有一个根元素通过一系列“邻居”关系连接到所有其他元素，所以有必须是 C 中的元素所在的边界点这导致 e 之后的 0 价配置是 C 中的元素的邻居导致 e 之后的一价配置.