FLP Impossibility

在 Fisher，Lynch 跟 Paterson 的一篇论文中，作者们描述了一个著名的 FLP Impossibility Problem (使用了几个作者名字的首字母命名)，他们讨论了处理一个具有初始化值并需要对一个新值达成共识处理。在这个算法完成后，新的值会在所有未出错的处理者保持一致。

为一个指定的值达成共识在完全可靠的网络中是比较直观的。但是在现实中，系统系统可能会因为各种不同的而发生故障，比如消息丢失、重复发送、网络分区以及可能有缓慢或者奔溃了的处理器。

共识协议描述了这样的一个系统，将多个处理器从一个初始化的状态启动，然后将他们全部都进入 Decision state 抉择状态，为了保证共识协议的正确，需要保持下面的三个属性：

  • Agreement

    协议所作的决定必须是一致的：每个处理器所选择的某个值必须是相同的，否则的话就无法达成共识

  • Validity

    被同意的值需要是其中一个参与者提出来的，这表示系统不会凭空产生出一个值。这同样意味着这个值不会是无意义的：处理器不应该总是选择那些预定义好的默认值

  • Termination

    只有在没有处理器未能做出决策的状态下，才能得到最终的共识结果。

论文还假设整个处理的过程都是异步的：处理的过程中处理器之间没有共享的概念。算法在这样的系统中不能够依赖于超时，处理器也没有办法去确认其他的处理器是崩溃了还是运行得太慢。论文展示的是，基于这些假设，现存的协议没办法在指定的时间边界内达成共识。没有完全异步的共识算法会连一个远程节点的突然崩溃都无法容忍。

如果我们不考虑完成这个算法各个步骤所需的时间上界，处理器的故障就无法可靠的检测到了，也就没有明确的算法能够达成共识了。

但是 FLP Impossibility 不意味着因为共识不可能达成我们要就这样拍拍屁股回家，他只是说我们没办法在具有时间边界的异步系统中达成共识。在实践中，系统在一定的程度上能够表现出同步性，而这个问题的解决方案也需要我们去把这个模型在定义的更精确些。