本片内容就要正经的讨论下paxos算法了。很复杂，不好理解。我还没读完。 只看到了基础的三定理，推导一致性的证明第一步。

首先，在说明三定理之前，先说明一些内容。 这会还处在迷信时代，是神职管理，为了容易理解，我都叫法案吧。

关键字

先解释下几个关键的符号。 1. $B{dec}$是指一次投票要表决的内容， 2. $B{qrm}$是指非空参与投票者，（注意，是参与投票，最终不一定投同意票） 3. $B{vot}$与上面相近，不过这个是指投同意票的 4. $B{bal}$是本轮投票的序号 从我们直观理解，可以知道$B{vot}\in B{qrm}$。也就是说，如果$B{qrm} \subseteq B{vot}$的话，则是全票通过，这次表决成功。（这个地方后面会有使用） 好了，我们继续往后面说。

三条定理

为了保证结果的一致性，只要满足以下三个条件即可 1. 任意两次投票的序号$B{bal}$一定不相同 2. 任意两次投票的$B{qrm}$一定有交集 3. 本次的$B{dec}$的值，与$B{qrm}$参与的最新投票的法案内容相同。

看起来很蒙，我们稍微来解释下。 第一条就是说两次投票，必有两个不同的序号，是为了保证不会重复 第二条也不是太难理解，就是保证每条法案都会有重合的人参与投票 第三条稍微难解释一点，就是说，这次参与投票的人（管他投没投同意票），以前如果参与过投票（注意，这个是得投了同意）的话，在这些人中一定有一个序号值最大的法案，这次的法案内容要跟它一样。 可能会有人问，为什么这三点能够保证一致性呢？别急，来看后续的证明。 当夜，也有人可能会问，谁想出来的这三点？Lamport说是Paxon想出来的。

证明

本部分就是数学证明了，会比较枯燥，但是感觉对于理解Paxos很有意义。

变量

为了后续的证明，首先定义以下几个变量&&公式。

$v{pst}$:投票人 $v{bal}$:投票序号 $v{dec}$:投票内容/法案 $v{v{pst},v{bal},v{dec}}$ 其中，还有个空值定义

$$v{null}{v{pst}=nullp,v{bal}=-\infty,v_{dec}=Blank}$$

为了便于计算，我们再定义一个大小比较的关系 $$v{bal}<v^{'}{bal}=>v<v^{'}$$ 还有一个取值的关系MaxVote，定义如下 $$MaxVote(b,p,\beta)={v \in Votes(\beta):(v{pst}=p)\wedge (v{bal}<b)} \cup {nullp}$$ 如果是对一个集合进行操作，比如$MaxVote(b,Q,\beta)$,就是对Q进行遍历，找到最大$v{bal}$的投票。

数学表达

$$B1(\beta) \equiv \forall B,B^{'} \in \beta : (B \neq B^{'})=> (B{bal} \neq B^{'}_{bal})$$ $$B2(\beta) \equiv \forall B,B^{'} \in \beta : B{qrm} \cap B^{'}_{qrm} \neq 0$$ $$B3(\beta) \equiv \forall B \in \beta : (MaxVote(B{bal},B{qrm},\beta){bal} \neq -\infty => (B{dec}=MaxVote(B{bal},B{qrm},\beta){dec})$$ 为了证明一致性，我们先证明以下性质，如果一次投票成功了，那么后续的法案都跟这次相同

引理

假设$B_1(\beta),B_2(\beta),B3(\beta)$都正确，则 $$((B{qrm} \subseteq B{vot}) \wedge (B^{'}{bal}>B{bal}))=>(B^{'}{dec}=B{dec}),\forall B,B^{'} \in \beta$$ 证明需要分好多步，而且有的地方一下子还理解不了，Lamport大神并不做详细解释，哎。 证明这个引理，所使用的是反证法。为了方便证明，首先定义一个变量 $$\psi(B,\beta) \equiv { B^{'} \in \beta :(B^{'}{bal}>B{bal}) \wedge (B^{'} \neq B{dec})}$$ 为了证明，我们已知$B{qrm} \subseteq B{vot}$，也就是全票通过，然后假设$\psi(B,\beta) \neq 0$，也就是存在值。 接下来就开始我们的证明之路了。 1.$\exists C \in \psi(B,\beta),C{bal}=min{B^{'}{bal}:B^{'} \in \psi(B,\beta)}$ 这一步很容易理解，因为$\psi(B,\beta)$非空，而且是有限集合，没有什么难理解的。 2.$C{bal}>B{bal}$ 这个也不难理解吧，本身的定义就说明了这个情况。 3.$B{vot} \cap C{qrm} \neq 0$ 我们首先知道,$B{qrm} \subseteq B{vot}$，就是B这次全部都投票，又通过定理2知道任意两次投票必有交集，所以这两个一定不为空。 4.$MaxVote(C{bal},C{qrm},\beta){bal} \geq B{bal}$ 首先，我们由（3）知道，两者有交集,那么通过MaxVote至少可以取到$B_{bal}$,当然了，如果$B \cup \psi(B,\beta) \neq \beta$的时候，就可以说明$MaxVote>B_{bal}$,如果相等的时候，则恰好上一个$B_{bal}$是取的值。 5.$MaxVote(C_{bal},C_{qrm},\beta) \in Votes(\beta)$ 我们从第四个可以知道MaxVote`非空，而且，很明显，取到的法案集合也一定在$\beta$里面，所以很容易就可以得到这一步 6.$MaxVote(C{bal},C{qrm},\beta){dec}=C{dec}$ 根据定理3，我们就可以很容易的推测到这个结论。 我当时在看到这个的时候，稍微纠结了下引理和定理三的区别。这个用定理3证明，是因为定理3表示的是B和最接近的$B{bal}$一致，而引理要证明的是本次成功了，以后的都会一样。 7.$MaxVote(C{bal},C{qrm},\beta){dec} \neq B{dec}$ 首先根据定理6，我们知道$MaxVote = C{dec}$，而根据定义，可以知道$C{dec} \neq B{dec}$问题很容易就可以证明。 8.$MaxVote(C{bal},C{qrm},\beta)>B{bal}$ 从第七个我们可以知道，这是两个不一样的投票，因为他们的法案内容是不一样的。这样，我们就可以从定理1推出，这两个的序号一定不同，问题得证。 9.$MaxVote(C{bal},C{qrm},\beta) \in Votes(\psi(B,\beta))$ 从第八个可以知道，序列号大于$B{bal}$,而且法案值不同，根据$\psi$的定义，可以推测出结果 10.$MaxVote(C{bal},C{qrm},\beta)<C{bal}$ 这个不用多说，是定义 11.悖论 我们已经知道了,$C{bal}$已经是最小的了，但是存在一个法案仍然属于$\psi(B,\beta)$，与我们刚开始的假设相反，则引理得证。

理论1

$((B{qrm} \subseteq B{vot}) \wedge (B^{'}{qrm} \subseteq B^{'}{vot}))=>(B^{'}{dev}=B{dec})$ 这个证明不难，如果$B^{'}{bal}=B{bal}$，毫无疑问。如果不相等，就是刚刚的引理。 这个有什么含义呢？就是说，不管怎么样，一定会有个结果的，不会陷入死锁。

理论2

额，太长了，不想打了，说下含义吧。 这个的含义就是说，不管什么恶劣情况，一定会找到满足三个定理的表决，使得一致性进行下去。

好了，继续看，继续写。