并可以在阶段2中提出任何决议。它把客户端的下一条命令编号为141，并当作实例141的阶段2的决议。再把下一条编号为142，以此执行。
【注解*】
对于同一个leader而言，如果它在执行实例i中执行了阶段1，那么后续的执行实例就不需要再次执行阶段1了，而直接执行阶段2，原因如下：
1. 因为它提出的议案编号总是递增的，acceptor必定接受阶段1的prepare请求； 2. 每个实例都是独立运行的paxos算法，互不干扰，决议互相独立； 减少了一个阶段，效率也必定有所提高。 【end*】
在知道提出的命令141被选择之前，Leader可以提出命令142。它提出命令141的消息可能都丢失了，还可能在其他服务器知道leader提出命令141之前，命令142已经被选择了。 当leader在实例141的阶段2中没有收到期望的回应后，它将重传这些消息。如果一切顺利，它提出的命令将被选择。然而，也可能会失败，在命令序列中留下了一个间隔。一般来说，假设leader可以预取r个命令——也就是说，在命令1到i被选择之后，它就可以同步提出命令i+1, ?, i+r。那么最多可以产生r-1个间隔【容易理解，前面的r-1个命令都失败了】。 新选出的leader要为算法的无限个实例执行阶段1——在上面的场景中，是实例135-137，和139之后的所有实例【我的理解是，为了这些实例，它总共只需要成功的执行一次阶段1，理由见上面的注解*，当然多次执行也不会出问题，就像下面所说的那样】。它可以向其他的服务器发送一条简单的合理短消息，并为所有实例使用相同的议案编号。在阶段1，仅当acceptor已经收到了一个来自其它proposer的阶段2的消息时，除了简单的OK，它的回应会包含额外的消息，（在上述场景中，仅实例135和140是这样的【像前面所描述的，实例135-137和139执行的输出将决定实例135和140提出的决议】）。因此，服务器（作为acceptor）可以为所有实例回应一条简单的短消息。多次执行阶段1并不会出问题。
因为leader的失效和由此引发的选举应该是小概率事件，有效执行一条状态机命令的开销——达到对命令/决议的一致性——仅仅是一致性算法的阶段2的开销【又一次验证了阶段1并不需要多次执行】。可以证明，在允许失效的情况下，在所有的同类（一致性）算法中， paxos一致性算法的阶段2具有最小可能的【时间】复杂度[2]。因此paxos算法在本质上就是优化的。
上面对系统正常操作的讨论假设一直存在单个leader，除去在当前leader失效和选举新leader之间的一小段时间。在异常环境中，leader选择可能失败。如果没有服务器被选为leader，那么将不能接受命令。如果多个服务器都认为自己是leader，在同一个算法实例中，它们将都能提出议案，这可能会导致所有的议案都不能被选择。然而，安全属性是满足的——两个不同的服务器将永远不会在第i个状态机命令的选择上达成一致。选择单一的leader只是为了保证流程【避免冲突】。
如果服务器组可以变动，必须有方法能检测哪些服务器执行的是算法的哪些实例。最简单的做法就是让状态机自己检测。当前的服务器组可以作为状态的一部分，并能被原生的状态机命令修改。我们可以让leader预取r个命令，并将执行算法实例i+r的服务器组的状态设置成执行第i个状态机命令后的状态。于是你可以使用简单的重配置算法来进一步增强算法的可靠性【如果半数服务器同时失效，重配置机制也束手无策，然而这种概率太低了】。 【下面wiki的两篇文章也是paxos很好的参考资料，一篇中文，一篇英文，然而内容并不重复】 http://en.wikipedia.org/wiki/Paxos_algorithm
http://www.wikilib.com/wiki/Paxos????3?
【还有两个重要的问题就是如何选举leader，以及server间数据的同步，可以参看zookeeper的实现；这些内容整理好下次再单独发出来:)】
参考文献
[1] Michael J. Fischer, Nancy Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, April 1985.
[2] Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus when there are no faults—a tutorial. TechnicalReport MIT-LCS-TR-821, Laboratory for Computer Science, Massachusetts Institute Technology, Cambridge, MA, 02139, May 2001. also published in SIGACT News 32(2) (June 2001).
[3] Leslie Lamport. The implementation of reliable distributed multiprocess systems. Computer Networks, 2:95–114, 1978. [4] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, July 1978.
[5] Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133–169, May 1998.
本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sparkliang/archive/2010/07/16/5740882.aspx
