在已知的论文Impossibility of Distributed Consensus with one Faulty Process (JACM85)中，FLP（Fisher、Lynch 和 Paterson）证明了一个令人惊讶的结果，即没有完全异步的共识协议可以容忍甚至一个未通知的进程死亡。
在引理 3 中，在证明 D 包含 0 价和 1 价配置后，它说：
如果在一个步骤中一个结果来自另一个，则调用两个配置邻居。通过简单的归纳，存在邻居 C₀, C₁ ∈ C 使得 Dᵢ = e(Cᵢ) 是 i 价的，i = 0, 1。
我可以遵循整个证明，除非他们声称存在这样的 C₀ 和 C₁。你能给我一些提示吗？
De（应用于的元素后的可能配置集C）包含 0 价和 1 价配置（并且假定不包含二价配置）。
也就是说——e将每个元素映射C到 0 价或 1 价配置。根据 的定义C，必须有一个根元素通过一系列“邻居”关系连接到所有其他元素，因此必须存在一个边界点，其中C导致 0 价配置的元素e与中的元素C导致 . 之后的一价配置e。
定义一个映射f，使得f(C) = 0, ife(C)是 0 价，否则，f(C) = 1, ife(C)是 1 价。
因为e(C)不可能是二价的，如果我们假设D没有二价配置，则f(C)只能是 0 或 1。
从树中的初始二价配置开始排列可访问配置，树中必须有两个邻居 C0、C1 f(C0) != f(C1)。因为，如果不是，所有f(C)都是相同的，这意味着D只有所有 0 价配置或所有 1 价配置。
我曾经走上阅读所有这些论文的道路，却发现这完全是浪费时间。
结果一点也不奇怪。
您提到的论文“[不可能的分布式共识与一个错误的过程]” 1
是一长串复杂的数学证明，简单地等同于：
1) 共识是一种确定性状态
2）环境中的一个（或多个）故障系统是非确定性环境
3) 在非确定性环境中永远无法达到确定性状态、行动或结果。
结束。无需进一步思考。
这就是它在学术界之外的现实世界中的运作方式。
如果您希望代理达成共识，则必须添加同步（时序模型）近似构造，以使环境在给定的一组约束内具有确定性。例如简单的结构，如 Timeouts、Ack/Nack、Handshake、Witness，或更复杂的结构。
您希望越接近同步确定性模型，构造就越复杂。假设的同步模型将具有无限复杂的构造。还要记住，在非平凡的分布式系统中永远无法实现完全确定的同步模型。这是因为在任何具有可变初始状态的非平凡动态多变量系统中，在任何时间点都存在无限数量的可能状态、动作和结果。混沌理论
考虑一个构造的复杂性，该构造用于检测由于跳数为 21 的路由器中的缓冲区溢出错误而丢弃的 TCP 数据包。以及检测从构造本身丢弃检测信号的相同缓冲区溢出错误的复杂性。