问题描述
在已知论文中，FLP（Fisher，Lynch和Paterson）证明了令人惊讶的结果，即即使一个未经通知的进程死亡，也没有完全异步的共识协议可以容忍。
In the known paper Impossibility of Distributed Consensus with one Faulty Process (JACM85), FLP (Fisher, Lynch and Paterson) proved the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death.
在引理3中，显示D包含0和1价配置后，它说：
In Lemma 3, after showing that D contains both 0-valent and 1-valent configurations, it says:
如果一个配置在另一个 step 中产生，则调用两个配置 neighbors 。通过简单的归纳法，存在邻居C₀，C₁∈C，使得Dᵢ= e（Cᵢ）为i价，i = 0，1。
我可以遵循整个证明，除非他们声称存在这样的C₀和C follow。你能给我一些提示吗？
I can follow the whole proof except when they claim the existence of such C₀ and C₁. Could you please give me some hints?
推荐答案
D （应用<$ c之后的可能配置集$ c> e 到 C 的元素都包含0-价和1-价配置（并且假定不包含二价配置）。
D (the set of possible configurations after applying e to elements of C) contains both 0-valent and 1-valent configurations (and is assumed to contain no bivalent configurations).
即- e 映射 C 中的每个元素变为0价或1价构型。根据 C 的定义，必须有一个通过一系列邻居关系连接到所有其他元素的根元素，因此，必须是一个边界点，其中 C 中的一个元素在 e 与元素相邻之后导致0价配置在 C 中导致 e 之后为一价配置。
That is — e maps every element in C to either a 0-valent or a 1-valent configuration. By definition of C, there must be a root element that is connected to all other elements by a series of "neighbour" relationships, so there must be a boundary point where an element in C that leads to a 0-valent configuration after e is neighbours with an element in C that leads to a 1-valent configuration after e.
这篇关于FLP不可能结果证明中存在0和1价结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！