Paxos: Responding to Reordered Prepare Requests 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 &gt; 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?
Correct. Another way to think about Paxos is as a two step process: 


Gaining permission to propose a value
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.