I was studying Paxos from:
http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf
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
