FLP（Fisher，Lynch和Paterson）在已知文章Impossibility of Distributed Consensus with one Faulty Process (JACM85)中证明了令人惊讶的结果，即完全异步共识协议甚至可以容忍单个未通知的进程死亡。
在引理3，示出了$ d $同时包含0价和1价的配置后，它说：
呼叫两种配置邻居在单一步骤如果从其他结果。通过简单归纳，在C $中存在邻居$ C_0，C_1 \，使得$ D_i = e（C_i）$是i-价格，$ i = 0,1 $。
我可以按照除了整个证明：
我的问题：虽然它被认为是容易的，我不能证明这样$ C_0，C_1 $的存在。你能给我一些提示吗？
谢谢。
D（在将e应用于C的元素之后的可能配置集合）包含0价和1价配置（并且假定不含二价配置）。
也就是 - e将C中的每个元素映射为0价或1价配置。通过的C定义，必须有由一系列的“邻居”的关系连接到所有其他元素一个根元素，所以有必须是边界点，其中在C导致一个0价配置之后的元素e与C中的某个元素相邻，它会在e之后导致1-valent配置。
定义映射f（）：f（C）= 0如果e（C）是0价。否则，如果e（C）是1价的，则f（C）= 1。
由于E（C）不能是二价的，如果假设d没有二价结构中，f（C）只能是0或1。
排列在链从初始二价配置可访问的配置有，必须是f（C0）！= f（C1）链中的两个邻居C0，C1。因为如果不是，所有的f（C）都是相同的，这意味着D只有全部0价配置或全部1价配置。
我曾经走过阅读所有这些论文的路，只发现它完全浪费时间。
结果并不令人意外。
你提到“[分布式一致性的不可能性与一个故障 处理]” 1
纸张是一个长期复杂的数学证明，简单地等同于的列表：
1）共识是确定性状态
2）一种（或更多）的环境中出现故障的系统是一个非确定性环境
3）任何确定的状态，动作或成果C永远在非确定性环境中达成。
结束。不需要进一步考虑。
这是它如何在acadamia以外的现实世界中工作。
如果您希望代理商达成共识，那么必须添加同步（时序模型）近似结构以使环境在给定的一组约束内具有确定性。例如Timeouts，Ack/Nack，Handshake，Witness等简单的构造，或者更复杂的构造。
您希望得到同步确定性模型越接近结构变得越复杂。一个假想的同步模型会有无限复杂的结构。同时要记住，一个完全确定性的同步模型在一个不重要的分布式系统中是永远无法实现的。这是因为在任何具有可变初始状态的非平凡的动态多变量系统中，在任何时间点存在无限数量的可能的状态，行为和结果。 Chaos Theory
考虑到由于在跳数为21的路由器中的缓冲区溢出错误，检测到丢弃的TCP数据包的结构的复杂性。并且检测到相同的缓冲区溢出错误从构造本身丢弃检测信号的复杂性。
这个特定的引理是本文的核心，我观察到它在Herlihy的另一篇论文“等待自由同步”中被广泛用于证明同步对象的一致性编号。 – 2017-02-01 03:58:53