I was studying Paxos from:


and I was trying to understand page 4, specifically, the following paragraph:

"To maintain the invariance of $P2^c$, a proposer that wants to issue a proposal numbered n must learn the highest-numbered proposal with number less than n, if any, that has been or will be accepted by each acceptor in some majority of acceptors. Learning about proposals already accepted is easy enough; predicting future acceptances is hard. Instead of trying to predict the future, the proposer controls it by extracting a promise that there won’t be any such acceptances. In other words, the proposer requests that the acceptors not accept any more proposals numbered less than n. This leads to the following algorithm for issuing proposals."

Where condition $P2c$ is:

"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

(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."

I was specifically confused about the section I have in bold. I was confused why, if we want to develop some hypothetical consensus distributed algorithm, why do we need to know about higher sequence numbers that have not happened? What is the intuition behind that?

Sorry if my title is a little strange, I was not sure what was a good title for the question.

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research


1 Answer 1


The bold section is saying that before proposing a value know if a value is accepted or if there is a higher proposal number that is chosen by one of the majority. If there is a higher proposal number, the proposer needs to propose a higher number than that is already proposed. If a value is already accepted then majority should know if a value is accepted. The proposer accepts the value. The majority is because two majorities always overlap.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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