简介
PAXOS是为了在有机器挂掉的时候，也能让提案决议得到通过，而不用一直等待（2PC的做法）而产生。经常被用来选举MASTER（当原MASTER挂了的时候）。
实现的核心是，1.发出提案， 2.针对这个提案，收集PROMISE。
PROMISE里可能带了VALUE,可能是空。
如果收到的PROMISE超过一半，并且全为空。提议者可以自己定一个VALUE，进入ACCEPT阶段。
如果有不为空的，会选择提案号最大的V，当做自己的VALUE，进入ACCEPT阶段。
PAXOS 的V 什么时候会被确定？ 当大多数ACCEPT 都同意了一个V，并更新了自己VA,NA（落库）了。这个V就不会变了。
之后的努力都是对这个V 在所有机器上达成一致。
详细介绍
机器间备份的状态要一致。
2个机器初始状态一样，经过确定的操作，终止状态一致。
第一个naive的实现。
但是不能保证所有机器的OPS的顺序一致。
为了解决这个问题
但是这个OPS，BACKUP SERVER 机器挂了怎么办？
这就要用到上一章说的2PC
这个不SCALE，增加更多的机器反而使得性能更差。一个优化是读操作，就不备份了。只有WRITE去备份。
但是读如果去任一台机器读的话，可能会读到旧的。如下图。这个顺序又会有不一致。
上述3个CHANLLENGE， 第2个可能会发生 出现多个 primary， 第3个会在PRIMARY切换时，出现状态不一致。
所以既要保证R/W的正确，还要保证在FAILURE时的正确。
之前介绍的2PC，在一个机器挂了，就会一直等，等最简单，保证一致性会简单。但是你如果想要在一台机器挂了的时候，可以切换，继续做下去，这个就会复杂。
这个一致共识的目标，就是在超过半数的节点还好的时候，整个PROCESS不会被BLOCK。并且所有节点会对一个结果达成一致。
消息会丢失，消息会被多次发送，消息可能会重排序（因为在分布式网络中这些无法避免）
这里有个假设，消息不会被篡改。
这个算法在2P+1的NODE中，可以允许P个NODE FAILURE。
PAXOS因为其协议的复杂性，所以会和2PC结合起来用，如果在没有FAILURE的情况下，我们依然用2PC来解决问题。 如果出现了FAILURE，为了不用等待，就要用PAXOS。
PAXOS 的特点是正确和容错，但是它没法保证TERMINATION（理论上会有活锁，实际情况很难发生）。
2PC 有固定的TC， PAXOS有其中一个PROPOSER扮演一个TC。
Acceptor 类似于2PC 的NODE，参与者。进行表决。议案不要求所有人通过，当多数人通过，其他人都要服从。
Learner 最后负责把状态修改完把消息告诉CLIENT。
一个值的修改，可以讨论多次，所以PROPOSAL NUMBER 是讨论当前这个VALUE 第N次尝试。
什么情况下ACCEPTOR会见到比它更大PROPOSAL？
比如MESSAGE 会REORDER。
如果当前PID 大于之前的所有PID， 他会返回之前同意的最大的PROPOSAL NUMBER and VALUE。
对于一个ACCEPTOR，返回它同意过的最大值。如果没有同意过，就会返回NULL。如果看得P ID 太小，直接IGNORE。
Acceptor 还有一次机会来判断这个N是不是最大。如果是的话，就在ACCPEROT这里通过了，他会告诉LEADER 和 LEARNER ACCEPTED
为什么要按照上述的方式做呢？
下面介绍了几种失败的情况
NA,VA,NH 这3个值是一定要落库的。WAL。（write ahead log的方式）
然后看下面实现的伪代码。
一个最简单的情况。
有多个LEADER 会同时进入第2个PHASH，但是不会有多多个LEADER通过第2轮。
大多数的ACCEPT 收到了ACCEPT, N,V，并且ACCEPT了。这个V就被确定了。
但是很多MASTER 申请去做LEADER， Nh就会被反复更新的更大，造成活锁，造成无法TERMINATION。
但是再实际中，不会有这么皮的情况。LEADER都不会那么频繁，也可以加一个时间间隔去发起LEADER申请。
如果一个机器挂了，第一个提案结束了，结论有了。都到了第二个提案，这个节点才醒来，那么该如何追赶第一个提案的结果。
它前面那个PAXOS还没完成，他只要自己去做下LEADER就可以，他那个PROPOSAL，会被REJECTED,他再发一个大的PROPOSAL，别人会把之前同意过的值还给他，他就有了。
上图的意思，A发起提案1 给A,C（因为那时B挂了），他在ACCEPT后，挂了。这个时候C已经把自己的NA,VA设置成1，foo. 当B醒来后，他发起PROMISE，他会收到B的FOO，他的提案也只能是FOO了。最后会对FOO达成一致。不可能是别的。
也就是说有了MARJORITY的ACCEPT后，V就不能改了。
最后看一下PAXOS，是怎么运用在rsm里的。
主要是为了当一个MASTER（TC）挂了的时候，他们重新对LEADER的选举达成一致。一旦一个新的LEADER被选举出了，那么接下来还是用2PC来做。
