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?