In the paper, Paxos Made Simple, a proposer asks an acceptor to respond to a pre
ID: 662183 • Letter: I
Question
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?
Explanation / Answer
The answer is correct.
The another way for finding Paxos is a two step process as follows:
1. Proposing a value by gaining permission.
2. Proposing a value actually
The gaining of permission successfully from a majority of peers in proposing a value explicitly
precludes the possible values from any previous proposal which are accepted by a majority of endusers.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.