Paxos是一个分布式选举协议，被广泛用在很多分布式系统中，比如Google的Chubby，MegaStore，Linux的Ceph。它的目的是为了让一群机器通过选举的方式达成一个一致性的决议。比如现在有5台MySQL服务器，它们要选举一个Master出来（无人工干预），所有的数据修改请求都发给这个Master，其它的做为Slave，以备在Master死掉后自动顶上去。
Paxos协议将参与通信的主体分为两个角色：proposer和acceptor。分别各有多个。分布式选举协议的基本框架是：
一个proposer提出一个提案，然后把这个提案发给所有的acceptor。
acceptor可以选择接受或者拒绝这个提案。
一个提案如果被过半数的acceptor接受，那么此提案被选中（chosen）。
一个系统中可以同时有多个proposer提出多个提案，但是最终只能有一个被选中。并且应该至少有一个被选中。
选举过程中机器可能crash掉，或者网络中断，机器一会儿死了一会儿活了。但是无论如何，只要死掉的机器数不过半，选举就应正常进行下去。
Paxos协议是一个被公认的晦涩难懂的协议。但是今天突然发现，如果按照逻辑时钟的角度去阐述它，它就变得简单清晰了许多。下面介绍如何利用带逻辑时钟的RPC协议来实现Paxos。
基于逻辑时钟的RPC协议
为了让这套系统能正确运行，我们需要一个精确的时钟。由于操作系统的物理时钟经常是有偏差的，所以我们决定采用一个逻辑时钟。时钟的目的是给系统中发生的每一个事件编排一个序号。
逻辑时钟可以利用全局计数器来实现。我们可以找一台机器提供一个全局的计数服务。它只支持一个方法：incrementAndGet()。这个方法的作用是将计数器的值加一，并且返回增加后的值。我们将这个计数器称为globalClock。globalClock的初始值为0。
然后，系统中的每个其它机器，都有一个自己的localClock,它的初始值来自globalClock。
假设机器和机器之间通过request-response这样的模式通讯。每条网络消息的类型要么是reqeust，要么是response。response又分为两种：OK和Rejected。
我们规定无论什么类型的网络消息，都必须带有一个时间戳，时间戳取自这台机器的localClock。我们规定消息的接收方必须执行以下行为：
if(message.timestamp<localClock && message.type==“request”) reject(message);else{ localClock=message.timestamp; process(message);}简而言之就是：我们不处理过时的请求。并且利用网络间传输的消息作为时钟同步机制。一旦收到过时的请求，就返回Rejected类型的答复。
另外，我们要求时钟不能倒流。我们必须容忍机器突然crash。在机器重新起来之后，要么localClock从globalClock取一个新值，要么localClock每次更新的时候都必须写入到本地硬盘上，重启之后从那再读进来。我们偏向于第二种方案，因为我后面将会讲怎么去掉globalClock这个服务器。
Paxos协议
proposer和acceptor可以位于同一台机器上，但是它们必须有各自独立的localClock。
我们允许一个acceptor在一轮选举中接受多个提案，但是最终只有票数最高的那个会被选中(chosen)。
Paxos的Request信息分为两种：prepare和accept。
1. 设置时钟：proposer令localClock=globalClock.incrementAndGet()。
2. 发送prepare消息:proposer向所有acceptor发送一个prepare消息。接收方应返回它最近一次接受的提案，以及接受的时间，若在它还没有接受过提案，那么就返回空。proposer只有在收到过半数的response之后，才可进入下一个阶段。一旦收到reject消息，那么goto step1.
3. 构造Proposal: proposer从prepare阶段收到的所有提案中选取时间戳最新的一个。如果没有，那么它自己创建一个提案。意即：如果有人提名了，它就只能跟票。否则，它可以提名新的候选人。
4. 发送accept消息，请求接受此Proposal: proposer把提案发送给所有的acceptor，消息的时间戳取自localClock。acceptor只要检查消息时间戳合法，那么就接受此提案，把这个提案和当前时间戳写入到硬盘上，然后答复OK，否则拒绝接受。proposer若收到任何的reject答复，则回到step1。否则，在收到过半数的OK后，此提案被通过。注意：只有这个proposer知道此提案被通过了，其它的proposer和acceptor都不知道。
globalClock的实现
如果系统中每台机器都有一个唯一的整数Id，那么我们就不需要一台专门的机器来提供clock服务，每台机器存储一个本地的计数器就可以了。
每台机器的clock由(roundNumber,serverid)这两个整型字段组成。roundNumber初始值为1。不同的服务器之间roundNumber可以重复。不再有全局的clock服务。
clock支持以下三种操作：
自增操作：roundNumber++, serverid=self.serverid
比较操作：先比较round number,再比较serverid。
赋值操作：对roundNumber和serverid分别赋值。
因为serverId是唯一的，所以inc操作产生的时间戳肯定是唯一的。因为先比较round number，后比较serverid，所以inc可以保证每次总是产生一个更大的时间戳。赋值操作可能会导致时钟的serverid和自己真实的serverid不相符，但是这没有关系，下次执行自增操作的时候会纠正过来。
Paxos协议的改进
原始的Paxos协议几乎不可在实际环境中使用。很多人对它做了很多改进，可惜改进后是否正确往往是不知道的。因为原始的Paxos协议的证明就已经很复杂，如同天书。后来工程师所做的边边角角的改进，综合起来之后，更是让证明变得困难很多很多倍。下面简述一些比较典型的。