正在wiki上学习Paxos算法。因为全英文，理解起来有困难，所以这里做个小搬运，以便自己日后翻看。

角色

Paxos中,一个处理器可以同时扮演几种角色且不影响协议的正确性。角色可以分为以下几种:

1.Client

Client向分布式系统提出request，并等待回应。例如，向一个分布式文件服务器提出写请求

2.Acceptor(Voters)

Acceptor是作为"Memory"的存在。Acceptors被划进名为"Quorums"的组中，以组成员的形式存在。任何基于Acceptor的行为都要通过它所属的Quorum来传递

3.Proposer

Proposer拥护Client的request请求，试图说服Acceptor去接受；此外，它还扮演了Coordinator的职位，当冲突发生时推动协议前进

4.Learner

当一个Client Request被Acceptor同意时，Learner采取行动，运行Request，并向Client回应

5.Leader

Paxos允许一个特别的Proposer(即Leader)来make progress。

Basic Paxos

Basic Paxos是最为基本的Paxos协议，一个Basic Paxos可能会持续多个回合。一个成功的周期包括了如下的两个Phases:

Phase 1

Phase 1a: Prepare

一个Proposer负责发起提案，我们称之为"Prepare"，它只拥有一个id(n)。n必须大于此Proposer之前使用过的任何id。
然后它将这个 Prepare 发送给一个 Quorum。如果它没有与任何Quorum沟通成功，就不能进入下一个Phase。

Phase 1b: Promise

如果一个Acceptor接受了一个Prepare with id=n，它就必须查看它直接接收过的所有id的最大值n_max。有两种情况:

case1:

如果n > n_max，那么Acceptor就会回应一个Promise，保证自己忽略接下来所有 id < n的 Prepare。除此之外，如果Acceptor之前接收过其它 Prepare，就必须在 Promise 中包含最近的 id 和 value。

case2:

n <= n_max，Acceptor直接忽略此 Prepare

Phase 2

Phase 2a: Accept

如果一个Proposer收到足够的Promises,它就必须为它的Proposal设定一个value。如果所有Acceptor都没在之前接收过Proposal,v=它最先想要提议的值x;反之v=返回值中最大的一个。
接下来，Proposer向Quorum发送一个 Accept 信息 (n, v)。这个 Accept 应该被理解为 Request，意思是:"请接受这个提议吧！"

Phase 2b: Accepted

如果一个Acceptor接收到一个Accept且它并没有作出Promise,它就必须accept，且向Proposer和每个Learner回应一个 Accepted。否则，它就应该忽略。

Multi-Paxos

Basic Paxos会导致很多开销。然而如果存在一个稳定的Leader, phase 1就不必要了(也就是验证此Proposer与Quorum的连通性的过程)。
为了实现这个思想，Round 1中，同一个Leader会递增它的value值，从而使Basic Paxos的4-delays减少到2-delays。
总体实现思路大致就是一个或多个阉割版的Basic-Paxos，一次周期被称为一个 "instance" of a Basic Paxos。

Fast Paxos

Fast Paxos归纳总结了 Basic Paxos，减少了 end-to-end 消息延迟。在Basic Paxos中，request到 learning之间存在3个 message-delay。Fast Paxos允许2个 message-delay,但有一些附加要求:
1.系统必须包含3f+1个Acceptors，以允许最多f个faults
2.Client能够向多个目标提交request
Intuitively，如果一个Leader没有需要propose的value，那么Client就可以直接向Acceptor发送 Accept!请求(注意区别)。Acceptor的回应与Basic Paxos中一样。
如果Leader发现了冲突，它也能够发送Accept!请求以开启新的一轮。

待补充