FLP不可能结果证明中存在0和1价结构 [英] Existence of a 0- and 1-valent configurations in the proof of FLP impossibility result

问题描述

在已知论文中具有一个错误过程（JACM85）的分布式共识的可能性，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。

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 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价结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！