1. FLP impossibility背景
FLP Impossibility（FLP不可能性）是分布式领域中一个非常著名的结果，该结果在专业领域被称为“定理”，其地位之高可见一斑。该定理的论文是由Fischer, Lynch and Patterson三位作者于1985年发表,之后该论文毫无疑问得获得了Dijkstra奖。
顺便要提一句的是，Lynch是一位非常著名的分布式领域的女性科学家，研究遍布分布式的方方面面，对分布式领域有着极其卓越的贡献，其著有<
>一书，书中有非常严谨而简洁的逻辑讨论了许许多多的分布式算法。
FLP给出了一个令人吃惊的结论：在异步通信场景，即使只有一个进程失败，也没有任何算法能保证非失败进程达到一致性！
因为同步通信中的一致性被证明是可以达到的，因此在之前一直有人尝试各种算法解决以异步环境的一致性问题，有个FLP的结果，这样的尝试终于有了答案。
FLP证明最难理解的是没有一个直观的sample，所有提到FLP的资料中也基本都回避了sample的要求。究其原因，sample难以设计，除非你先设计几种一致性算法，并用FLP说明这些算法都是错误的。
2. 系统模型
任何分布式算法或定理，都尤其对系统场景的假设，这称为系统模型。FLP基于下面几点假设：
- 异步通信
与同步通信的最大区别是没有时钟、不能时间同步、不能使用超时、不能探测失败、消息可任意延迟、消息可乱序 - 通信健壮
只要进程非失败，消息虽会被无限延迟，但最终会被送达；并且消息仅会被送达一次（无重复） - fail-stop模型
进程失败如同宕机，不再处理任何消息。相对Byzantine模型，不会产生错误消息 - 失败进程数量
最多一个进程失败
- Termination（终止性）
非失败进程最终可以做出选择 - Agreement（一致性）
所有的进程必须做出相同的决议 - Validity（合法性）
进程的决议值，必须是其他进程提交的请求值
3. 一个Sample
4. Paxos为什么可以？
其实仔细回忆Paxos论文会发现，Paxos中存在活锁，理论上的活锁会导致Paxos算法无法满足Termination属性，也就不算一个正确的一致性算法。Lamport在自己的论文中也提到“FLP结果表明，不存在完全满足一致性的异步算法…”，因此他建议通过Leader来代替Paxos中的Proposer，而Leader则通过随机或其他方式来选定（Paxos中假如随机过程会极大降低FLP发生的概率）。也就是说Paxos算法其实也不算理论上完全正确的，只是在工程实现中避免了一些理论上存在的问题。但这丝毫不影响Paxos的伟大性！
5.定理证明
5.1 一些定义
- 消息队列：
假定存在一个全局的消息队列，进程可以发送消息，也可以在其上接收消息。
send/receive：send(p,m)是指给进程p发送消息m，只是放入队列，称”发送“，如果消息被p接收，成送达(delivery)；receive(p)：接收发送给p的消息，若没有则返回空
消息队列实际上是模拟了异步通信，即消息会被延迟、乱序 - Configuration：前面已经提到，所有进程的状态集合，进程的状态包括初始值、决议值、消息队列的内容
初始Configuration：各个进程初始值是随机的、消息队列为空、决议为空的开始状态 - 事件e=(p,m)
事件代表给某个进程发送消息，并且消息已经送达。正是因为执行了某个事件，导致Configuration变化为另一个Configuration - 事件序列run
一连串顺序执行的事件序列称为一个run - 可达Configuration
如果某个Configuration A执行了一个run得到另一个Configuration B，则称B从A可达
5.2 引理1（连通性）
【把所有的进程P分成两个不相交的集合P1，P2，有两个run R1，R2，如果先给P1应用R1，再给P2应用R2与先给P2应用R2，再给P1应用R1，对P的Configuration C来说得到的结果是一致的（结果显而易见，不再罗列证明）】
5.3 引理2（初始Configuration不确定性）
5.4 引理3（不可终止性）
5.4.1 证明的正规化
5.4.2 证明D中既包含决议为”提交“的Configuration，也包含决议为”回滚“的Configuration。也即证明D中的Configuration不是单值决议。
5.4.3 若D是”确定“的，则导出一个矛盾
i=e(C
i),i=0,1，是i-valent的。假设C
1=e
‘(C
0),e
‘=(p
‘,m
‘)：
‘，则D
1=e
‘(D
0)，根据连通性会导出一个矛盾（从D
0会到D
1，这显然是不可能的）：
‘，先看下图：
‘,e， 则会到达E1；如果对A应用e，则会到达E0。也就是说A是”不确定“的。这与C0是确定的Configuration矛盾，这导致最初的假设D是”确定的”错误，因此D是“不确定”的。
6. 总结
7. 参考资料
- Impossibility of Distributed Consensus with One Faulty Process
- http://the-paper-trail.org/blog/a-brief-tour-of-flp-impossibility/comment-page-1/#comment-
- Lynch的大作：<
>
- FLP_and_Paxos.pdf(Ken Birman)
- Ken Birman教书的网站：http://www.cs.cornell.edu/ken/
Origin
在处理和分析数据时，最理想的环境是这样的：
一台有无限存储和计算能力的“超级计算机”，可以提供无穷大的存储容量，并且可以将计算时间降低至无穷小。
《银河系漫游指南》中全宇宙全时空第二强的计算机“深思”，花费750万年时间，计算出了“宇宙、生命及万物 ”终极问题的答案：42
这样一台“超级计算机”在现实世界中并不存在。计算机的存储和计算能力始终要受到客观物理规律的限制。在可预见的将来，单位存储单元上无法存储超量的数据；而在运行计算任务时，由于芯片计算能力是有限的，当计算需求超过瞬时计算能力时，往往会发生排队现象。为了解决大量数据的存储和计算能力不足的问题，我们有两种选择：
扩展性 :增加机器不改变或极少改变系统行为，并能获得近似线性的性能提升；
性能 :指分布式系统进行服务时的延时和吞吐率是满足用户需要的；
可用性 :分布式系统的核心需求，表示分布式系统是否处于整体可服务并且一直可服务的状态；
容错性 :系统发生错误时，系统有对错误进行规避和恢复的能力。
保持一致 :系统中相关数据间的逻辑关系应当是正确和完整的。极端情况下，从系统中任意部分读取而获得的数据应当都为最近写入的数据；
处理失效 :分布式系统可能出现的失效状况有三类：节点失效、网络分区失效、拜占庭失效。极端情况下，系统的执行和操作不会受到任何系统内部失效的影响；
时钟同步 :分布式系统有两种模型：同步系统和异步系统。同步系统会确保所有执行过程的步调一致，且各执行过程有精确的时钟。即任意处理过程能够得到精确的执行流程的偏序关系，也就意味着每个处理过程和通信都在有限的时间内进行。异步系统则相反，没有任何时序性保证。即各处理过程是完全以自己的节拍在运行，不存在有效的同步时钟，也意味着过程间的通信延时可能会趋于无穷大。
一致（Agreement） :每个正确的执行过程应该在相同的值上达成一致；
完整（Integrity） :每个正确的执行过程最多只能决定一个值。如果它决定了某个值的话，这个值一定是被某个执行过程提出的；
终止（Termination） :所有的执行过程最终会做出一个决定；
正确（Validity） :如果所有正确的执行过程提出了相同的值V，那么所有正确的执行过程都会决定值V。
FLP不可能性
在假设网络可靠、计算节点只会因崩溃而失效的最小化异步模型系统中，仍然不存在一个可以解决一致性问题的确定性算法。
CAP定理
分布式计算系统不可能同时确保一致性、可用性和分区容忍性。
一致性（Consistency） :所有节点在同一时刻能够看到同样的数据，也即“强一致性”；
可用性（Availability） ：确保每个请求都可以收到确定其是否成功的响应；
分区容忍性（Partition tolerance） :因为网络故障导致的系统分区不影响系统正常运行。
C+A ：以2阶段提交(2 phase commit)为代表的严格选举协议。当通信中断时算法不具有终止性（即不具备分区容忍性）;
C+P ：以Paxos、Raft为代表的多数派选举算法。当不可用的执行过程超过半数时，算法无法得到正确结果（即会出现不可用的情况）;
A+P ：以Gossip协议为代表的冲突解决协议。当网络分区存在和执行过程正确时，只能等待分区消失才保持一致性（即不具备强一致性）
参考资料
一致性问题：https://en.wikipedia.org/wiki/Consensus_(computer_science)
FLP不可能性：http://cs-www.cs.yale.edu/homes/arvind/cs425/doc/fischer.pdf
CAP定理：https://en.wikipedia.org/wiki/CAP_theorem
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/208392.html原文链接：https://javaforall.net
![SP论坛天堂鸟技术学院[通俗易懂]](https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg)
