PAXOS

paxos make simple, 描述的过程是一步步加强协议直到满足一致性要求

P1

An acceptor must accept the first proposal that it receives.

P2

If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

P2a

If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

满足了p2a可能还会出现下面这种情况，所以还需要加强限制到P2b:

We still maintain P1 to ensure that some proposal is chosen. Because communication is asynchronous, a proposal could be chosen with some particular acceptor c never having received any proposal. Suppose a new proposer “wakes up” and issues a higher-numbered proposal with a different value. P1 requires c to accept this proposal, violating P2a . Maintaining both P1 and P2a requires strengthening P2a to:

P2b

If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v

当选了一个值v后，所有之后新的proposal的值都是v

为了满足P2b引出了P2c

P2c

For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either

• no acceptor in S has accepted any proposal numbered less than n：还没有任何acceptor在S中
• v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S：v 是集合S中的acceptor所接受的值

这里引入一个集合S，用于表示大部分接受了值v的acceptor.

To maintain the invariance of P2c , a proposer that wants to issue a proposal numbered n must learn the highest-numbered proposal with number less than n：就是说如果要提出一个新的proposal n，必需要先取得前面被接受的proposal number小于n的最大的proposal number

prepare

通过上面的需求加强，引出了一个新的东西：prepare:

A proposer chooses a new proposal number n and sends a request to each member of some set of acceptors, asking it to respond with:

• A promise never again to accept a proposal numbered less than n, and
• The proposal with the highest number less than n that it has accepted, if any.

前面说的都是proposer的约束，下面说的是acceptor

P1a

An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n: acceptor能接受proposal n的前提条件时它没有回复一个number的值大于n的prepare request. 没有回复比n大的proposal, n < 已经回复的最大n

Algorithm

Phase 1.

• A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
• If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.

Phase 2

• If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
• If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

Learning a Chosen Value

怎么确定value?