3
$\begingroup$

In the paper, Paxos Made Simple, a proposer asks an acceptor to respond to a prepare request with:

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

Therefore:

[An acceptor] can receive two kinds of requests from proposers: prepare requests and accept requests. An acceptor can ignore any request without compromising safety. So, we need to say only when it is allowed to respond to a request. It can always respond to a prepare request. It can respond to an accept request, accepting the proposal, iff it has not promised not to.

Next, Lamport offers this optimization:

Suppose an acceptor receives a prepare request numbered $n$, but it has already responded to a prepare request numbered greater than $n$, thereby promising not to accept any new proposal numbered $n$. There is then no reason for the acceptor to respond to the new prepare request, since it will not accept the proposal numbered n that the proposer wants to issue. So we have the acceptor ignore such a prepare request.

Suppose an acceptor receives a prepare request numbered $n$, but it has responded to a prepare request numbered $n + 1$ and accepted the proposed value (the prepare request for proposal $n$ was delayed arbitrarily by the network). The acceptor has thus promised never to accept a proposal numbered less than $n + 1$. However, we know that:

an acceptor can always respond to a prepare request.

Therefore, the acceptor can respond with a promise never to accept a proposal numbered less than $n$ since it has already made a promise never to accept a proposal numbered less than $n + 1$, however it cannot respond to the prepare request for proposal number $n$ with the proposal $n + 1$ because it must respond with:

The proposal with the highest number less than $n$ that it has accepted.

Since $n + 1 > n$ it can respond with no proposal. This would enable both the proposer of proposal number $n$ to choose a value, and the proposer of proposal number $n + 1$ to choose a value. However, even in the case where the proposer of $n$ sent their accept request before the proposer of $n + 1$, the accept request would be ignored because a majority has promised not to accept a proposal numbered less than $n + 1$. Thus, safety is still guaranteed. Is this correct?

$\endgroup$
3
$\begingroup$

Correct. Another way to think about Paxos is as a two step process:

  1. Gaining permission to propose a value
  2. Actually proposing a value

The act of successfully gaining permission from a majority of peers to propose a value explicitly precludes the possibility of any previous proposal from being accepted by a majority of peers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.