Paxos Made Simple

FLP

Impossible for a deterministic protocol to guarantee consensus in bounded time in an asynchronous distributed system (even with only one faulty process)

Assumption

Asynchronous environment: no bounds on timing.

• Each agent operates at an arbitrary speed, can fail and restart.
• Messages can be delayed, lost, duplicated, but cannot be corrupted.
• There is a sufficiently long period without further failures

non-Byzantine failure.

How many replica Paxos needs to tolerate f failures.

n-f > n/2 => n>2f => n = 2f+1

Safety and Liveness

Goal

The goal is to make sure acceptors achieve consensus on a single value.

Liveness

The proposed value is eventually chosen.

If a value is chosen, a process eventually learns it.

Safety

only a single value can be chosen

The learner can only learn the chosen value.

Paxos ensures

Paxos can provide safety properties by using unique proposal numbers.

Init Paxos cannot guarantee liveness,

Liveness can therefore be achieved by electing a single distinguished proposer

Proposer’s Action

Rule

Single acceptor fails to lead to no value being chosen => break liveness =>

Rule 0: A value is chosen only when it is accepted by a majority of acceptors.

Acceptors must accept a value otherwise the system can be blocked forever => break liveness =>

P1. An acceptor must accept the first proposal that it receives.

But multiple values can be proposed at the same time, one value is accepted by half of them and another value is accepted by another half of them, leading to no value being chosen.

The acceptor must be allowed to accept more than one proposal and the proposal is labeled with number <value, number>

• Proposal numbers must be unique and infinite
• A proposal number server won’t work
• Instead, assign each proposer an infinite slice
• Proposer i of N gets: i, i+N, i+2N, i+3N, …

If acceptors can accept many proposals, then how to make sure only one value is chosen (guarantee safety) =>

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

Above requires A proposal must be accepted by at least one acceptor =>

P2a. If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v (if a new proposal don’t have value V, it is ignored)

If the majority has accepted value v1, but the left agents have never accepted any value yet, according to P1, if a new proposal with v2 comes, the left agents accept it. Which is in conflict with P2a.=>

P2b. If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v. (in sending, it must have v since it is chosen)

How to make sure the proposal knows which value is chosen or if no value is chosen =>

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

(a) no acceptor in S has accepted any proposal numbered less than n, or

(b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

Discussion

If v1 is chosen by the majority, then

P2c(propose figure out v1 is chosen) => P2b(can only send v1) => P2a(can only accept v1) => P2( can only choose v1 )

P2c means if a proposal send (v,n), then either

1. the majority has not accepted any value yet.
2. the majority has accepted value v, and the new proposal n is the latest proposal.

To maintain P2c, a proposer that wishes to propose a proposal numbered n must learn the highest-numbered proposal with a number less than n, if any, that has been or will be accepted by each acceptor in some majority of acceptors =>

Implementation Algorithm

Prepare request

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) A promise never again to accept a proposal numbered less than n, and

(b) The proposal with the highest number less than n that it has accepted, if any.

Accept request

If the proposer receives the requested responses from a majority of the acceptors, then it can issue a proposal with number n and value v, where v is the value of the highest-numbered proposal among the responses, or is any value selected by the proposer if the responders reported no proposals.

Acceptor Action

P1a. An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

(n prepare - accept ), (n+1 prepare - accept ), (n+2 prepare - accept )

• if n+1’s prepare is accepted, the acceptor ignore n’s accept request,

  this situation may break the liveness when the acceptor always rejects the accept request due to higher prepare request coming.

  solution is to elect a leader proposer, and allow only it to propose value.

• if n hasn’t reply n+1’s prepare request, it can still response n’s accept request.

• Optimization: if n+1's prepare is accepted, n's accept ignore n+1's duplicated prepare request

Acceptor remember only

1. the highest-numbered proposal that it has ever accepted
2. the number of the highest-numbered prepare request to which it has responded.

Algorithms

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.

Optimization: It should probably inform the proposer, who should then abandon its proposal. This is a performance optimization that does not affect correctness.

Learner

More generally, the acceptors could respond with their acceptances to some set of distinguished learners, each of which can then inform all the learners when a value has been chosen.

Progress

if p1 and p2 propose at the same time, p1 send prepare request n1, p2 send prepare request with n2. then acceptor ignore n1’s accept after receiving n2’s prepare, p1 then propose n3 prepare, acceptor refuse n2’s accept and so on.

To guarantee progress, a distinguished proposer must be selected as the only one to try issuing proposals

Implementation

Collection of clients and servers.

Each server independently implements a deterministic state machine.

One server is the leader (distinguished proposer)

Client send cmd to leader.

---

• ← Previous Post
• Next Post →