The problem
Assume a collection of processes that can propose values. A consensus algorithm ensures that a single one among the proposed values is chosen. If a value has been chosen, then processes should be able to learn the chosen value.
The safety requirements for consensus are(通过以下三个约束,获得Paxos共识算法):
• Only a value that has been proposed may be chosen. (决议(value)只有在被 proposers 提出后才能被批准)
• Only a single value is chosen.
• A process never learns that a value has been chosen unless it actually has been. (learners 只能获得被批准(chosen)的 value)
Notice:
- some proposed value is eventually chosen and, if a value has been chosen, then a process can eventually learn the value.
- Paxos is a consensus(共识) algorithm not consistency(一致性) algorithm.
Message Model
Assume that agents can communicate with one another by sending messages. We use the customary asynchronous, non-Byzantine model, in which:
• Agents operate at arbitrary speed, may fail by stopping, and may restart.
• Messages can take arbitrarily long to be delivered, can be duplicated, and can be lost, but they are not corrupted.
Algorithm
Roles
There are three roles in the consensus algorithm:
roposer: sends a proposed value to a set of acceptors. (决议(value)只有在被 proposers 提出后才能被批准)
Acceptor: accepts a proposed value. The value is chosen when a large enough set of acceptors have accepted it.
Learner: only knows the chosen value.
Notice:
- In an implementation, a single process may act as more than one agent(允许身兼数职).
- majority == quorum
Choosing a value
Phase 1.
(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
(b) 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.
(a) 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.
(b) 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
To learn that a value has been chosen, a learner must find out that a proposal has been accepted by a majority of acceptors.
1.The obvious algorithm is to have each acceptor, whenever it accepts a proposal, respond to all learners, sending them the proposal. This allows learners to find out about a chosen value as soon as possible, but it requires each acceptor to respond to each learner—a number of responses equal to the product of the number of acceptors and the number of learners.
2.We can have the acceptors respond with their acceptances to a set of distinguished learners, which in turn informs the other learners when a value has been chosen. Using a larger set of distinguished learners provides greater reliability at the cost of greater communication complexity.
Because of message loss, a value could be chosen with no learner ever finding out. The learner could ask the acceptors what proposals they have accepted, but failure of an acceptor could make it impossible to know whether or not a majority had accepted a particular proposal. In that case, learners will find out what value is chosen only when a new proposal is chosen. If a learner needs to know whether a value has been chosen, it can have a proposer issue a proposal, using the algorithm described above.
…