Consensus共识的定义：
termination终止性: 所有进程最终会在有限步数中结束并选取一个值, 算法不会无尽执行下去.
agreement一致性: 所有进程必须同意同一个值.
validity有效性/合法性: 最终达成一致的值必须是V1到Vn其中一个, 如果所有初始值都是vx, 那么最终结果也必须是vx.
排除拜占庭问题，只考虑异步通信下的宕机-恢复故障模型：消息系统是异步的, 但是任何消息都会被接收一次且仅一次, 并且无法伪造或者丢失。这是比一般的异步网络更加可靠的一个网络模型. 这样收窄的一个模型如果在只有一个faulty进程的情况下都不能有一个完全正确的共识协议, 那么在更一般的异步网络或者包含Byzantine故障的模型里，更不可能在有一个faulty进程的情况下有完全正确的protocol. 这里完全正确(totally correct)是指同时满足safety和liveness. 在实际应用中, Paxos, Raft, PBFT都是保证safety但是不保证liveness的, 所以他们都不是完全正确的算法, 理论上存在进入无限循环的可能性(实际上概率非常低, 在工程中完全可以使用). 在当时可以说这是一个非常令人震惊的结论了, 给我们日常工程中很多问题判了死刑，比如分布式系统的缓存一致性和可用性，比如分布式事务的一致性和可用性等等.
一个Sample：假设有A、B、C、D、E五个进程就是否提交事务为例，每个进程都有一个随机的初始值提交（0）或回滚（1）来向其他进程发送请求，进程自己必须接收到其他进程的请求后才能根据请求内容作出本地是提交还是回滚的决定，不能仅根据自己的初始值做出决定。如果所有的进程都做出相同的决定，则认为一致性达成（Validity属性）；根据前面的系统模型，允许最多一个进程失败，因此一致性要求要放松到允许非失败进程达成一致。当然，若有两个不同的值被不同的进程选择，则认为无法达成一致。
现在目标是要设计这样一个算法，保证符合上述三个属性，并允许最多一个进程失败。
假如我们设计一个算法P，每个节点根据多数派表决的方式判断本地是提交还是回滚：
假如C收到了A、B的提交申请，收到了D的回滚申请，而C本身也倾向于回滚，此时，提交、回滚各有两票，E的投票决定着C的最终决议。而此时，E失败了，或者E发送给C的消息被无限延迟（无法探测失败），此时C选择一直等待，或者按照某种既定的规则选择提交或失败，后续可能E正常而C失败，总之，导致C没有做出最终决策，或者C做了最终决策失败后无人可知。称所有进程组成的状态为Configuration，如果一系列操作之后，没有进程做出决策称为“不确定的”Configuration；不确定Configuration的意思是，后续可能做出提交，也可能做出回滚的决议。
相反，如果某个Configuration能准确地说会做出提交/回滚的决议，则称为“确定性”的Configuration（不确定/确定对应于原论文中的bivalent/univalent）。如果某个Configuration是确定的，则认为一致性是可以达成。
对上述算法P，可能存在一种极端场景，每次都构造出一个“不确定”的Configuration，比如每次都是已经做出决议的C失败，而之前失败的E复活（在异步场景中，无法真正区分进程是失败，还是消息延迟），也就是说，因为消息被延迟乱序，导致结果难以预料！
而FLP证明也是遵循这个思路，在任何算法之上，都能构造出这样一些永远都不确定的Configuration，也就没有任何理论上的具体的算法，能避免这种最坏情况。
定义：
message buffer：系统共用的消息队列。支持两个操作 ①send（p,m）:把一个消息（p,m）放入message buffer。②receive(p): p从message buffer删除并取得消息值m, 或者返回null. 前者表示消息被接收到, 如果message buffer为空后者表示没有p的消息, 如果message buffer不为空表示p的消息传输被延迟. 注意, p的消息被延迟的次数有上限, 任何消息最终都会被收到.
configuration：整个系统的状态：决议，所有进程的内部状态，message buffer状态
faulty进程：可能在一系列操作后，最终停止的进程
决议：进程接收到其他进程的请求后才能做出决议，不能仅靠自身的初始值。决议Yp有三种可能 0 ，1 ，b（不确定）。只要有一个non-faulty进程做出决议Y0或Y1，认为整个configuration做出决议（因为要求算法保证不能出现两个不同的决议值）。一个configuration若无论后面发生什么事件，都会选择0，则叫0-valent（等价于一个进程做出决议Y0）。若都会选择1，则叫1-valent。若必须依赖后续事件才能确定，则叫bi-valent。
Lemma1连通性：
这条引理表示如果一个C里有两组事件, 每个事件(p, m)分别是在两组没有交互的进程上, 那么先使用任何一组事件再使用另外一组事件在C上, 结果都一样. 下图描述了这样的情况.
这个引理太容易理解了, 就不做证明了. 不过我们可以举个例子来描述一下: 比如Paxos的两阶段算法中, 假设有A, B, C, D，E五个节点, 𝞂1是B收到了A的第一阶段消息, 𝞂2是D/E收到了C的第一阶段消息(假设网络有延迟，D/E还没收到A的第一阶段消息，B还没收到C的第一阶段消息). 因为A/B是一组进程, C/D/E是一组进程, 𝞂1和𝞂2分别作用于这两组不相交的进程上.那么无论是先𝞂1, 𝞂2的顺序被送达还是按照𝞂2, 𝞂1的顺序, 最终结果都是C3。前面模型中提到的message buffer可能返回空就很好的模拟了这种消息延迟或者短暂的发生网络分区的情况.
Lemma2初始configuration不确定性：【对任何算法P都存在一个不确定性的初始Configuration（从该Configuration即可到达提交也可到达回滚，参考上面smaple）】
这个引理主要是为了说明，不是所有的决议结果都由初始值决定。如果所有进程的初始值都为“提交”，则决议值肯定为“提交”；相反若都为“回滚”则决议为“回滚”，但如果初始值随机化后，因为消息的延迟，最终的决议值就可能是“提交”也可能是“失败”（不确定性），这个引理也揭示了异步消息的本质特征。
反证法，假如所有的初始Configuration都是确定性的，即一些决议值必定为“提交”，而另一些一定是“回滚”。如果两个Configuration只有一个进程的状态有差别，则称为相邻，把所有Configuration按相邻排成一个环，则必定存在一个Configuration C0和C1相邻，并且C0是决议“提交”，C1决议“回滚”。
假如某一个Run R导致C1最终的决议值为“回滚”，根据系统模型，允许最多一个进程失败，我们就假设C0和C1的连接进程P发生失败。刨除P后，C0和C1的内部状态应该完全一致，这样Run R也可应用于C0，也会得到与C1同样的决议结果：“回滚”。这与C0是“提交”的结果矛盾，因此，必定存在“不确定”的初始Configuration。
证明严密而巧妙，其中构建相邻环和基于最多一个进程失败的假设是关键。构建环的方法还会在后续证明中用到。
lemma3不可终止性（不确定传播性）：【从一个“不确定”的Configuration执行一些步骤后，仍可能得到一个“不确定”的Configuration】
e=（p，m）代表p收到m消息，e=（p，null）代表p没收到消息
所有进程比如p必须要根据e的结果才会发生变化（e=（p,m）或e=（p,null）），发出新的e或者得出决议。
所有的共识算法无非如此：①进程发出msg向其他进程通信 （发出许多e） ②根据e的结果处理的逻辑（接收到某些msg，就能做出决议，或者无法决议等待或再发出msg通信）
Lemma3意思是：任何算法在得到一个不确定的Configuration后（为什么不确定？因为卡在某个阈值，有个一msg因为延迟或者宕机没接到），无论怎么玩（各种操作去处理），当卡在那个阈值的msg到达后，仍可能得到一个不确定的Configuration。
因为异步环境中无法确定是延迟还是宕机导致e不到达，所以e总可能后续到达，只要证明在某个时刻e到达能导致 bivalent configuration这个小圈，上面说的【从一个“不确定”的Configuration执行一些步骤后，仍可能得到一个“不确定”的Configuration】大圈也就证明了
再说明一下：就是任何算法P总有可能从bivalent configuration一通操作后又变成 bivalent configuration，就有可能一直无法得到共识。
先说明一下证明的方向
Cb（bivalent configuration 因为e=（p,m）每到达所致），接下来算法会一系列的操作来试图变为0/1-valent（让某一个进程做出决议即可），假设算法设定进程p做出决议需要n步（n次get e的结果），e=（p,m）可能在任意一步后到达 ，所有e到达后的D configuration 只要有一个bivalent configuration ，就又回到了Cb，循环起来，总有可能无法得出决议。
用反证法，证明 所有D组成的集合 ‘D中全是0-valent或1-valent 为假命题即可。
证明：（反证所设前提 ‘D中全是0-valent或1-valent ）
证明分3步，第一步先证明所有通过e可能得到的D 的集合‘D中一定有0-valent与1valent两种。
把还没收到e=（p,m）时，C可达的configuration 集合叫ε[configuration]。
因为C 为bivalent configuration ，所以C可达E0(0-valent) ，也可达E1(1-valent)。先看E0，如果e在做出决议0-valent后到达，则D一定是0-valent的（因为已经做出了决议，后续不管咋玩0-valent都不会变）。如果e在做出决议0-valent前到达，因为‘D中全是0-valent或1-valent,所以 D一定是0-valent（同样也是因为已经做出了决议，后续不会变化） 。E1同理，既然C可达E0与E1，所以‘D中一定有0-valent与1valent两种。
第二步，从ε中找两个configuration，C’与C''，使C‘通过一条消息e’= (p’, m’)得到C''(和lemma2一个道理，不过lemma2是以一个进程状态为单位，这里用一个e做单位，总有相邻的C’和C‘’差一个e‘，得到不同的决议)
D0（0-valent）通过e'变成了D1（1-valent），显然不可能
情况2：e与e’作用于相同的进程p，假设p is faulty（p出了问题，所有作用于p的e都不会改变系统的configuration）,肯定有一系列事件𝞂（不包含作用于p的事件）可以使C0变为A（确定的configuration ，0 或者 1）。所以𝞂与e作用的进程不向交，又可以用到Lemma1：A即可以变成E0，又可以变成E1.矛盾。（后面e，e'发生时 p恢复了）
至此p=p’和p!=p’的两种情况在我们的反证假设下都矛盾, 因此反证假设错误. Lemma 3 证明完成, 即: Ɗ 一定包含bivalent configuration.
三个Lemma都证明结束后, 我们来推导最终FLP定理.
根据Lemma 2, P一定含有bivalent initial configuration, 那么任何从这个bivalent状态进入univalent的deciding run, 其中必然存在一个从bivalent到univalent的关键步骤, 这个步骤决定了最终结果. 我们接下来就是要证明系统中总是有可能会把这个步骤无限推迟下去.
我们设计一个队列, 把所有进程放到这个队列中, 按照FIFO的顺序每次一个进程出来, 这个进程从message buffer取出第一个此进程的消息, 把计算后发给其他进程的消息放回message buffer尾部, 然后进程自己回到队列尾部等待下一轮调度. 这个模型保证了每个进程总是有机会获得发送给他的消息. 根据Lemma 2我们知道一定会存在一个bivalent的configuration C0, 从C0开始执行到某一个bivalent的C, 这时候message buffer中第一个C的消息是e. 再根据Lemma 3我们知道如果把e挪到message buffer后面延迟这个消息的送达, 那么C一定会再产生一个bivalent configuration C’进入Ɗ. 这意味着通过延迟e, 可以让一个bivalent configuration再产生一个bivalent configuraiton, 因为可能会永远无法达到一个univalent configuration, 也就永远无法产生结果.
