I'm reading the paper Paxos made simple but got stuck on the proving part for P2b.
Content of rule P2b:
If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.
And this is the proving part by Leslie Lamport:
To discover how to satisfy P2b, let’s consider how we would prove that it holds. We would assume that some proposal with number m and value v is chosen and show that any proposal issued with number n > m also has value v. We would make the proof easier by using induction on n, so we can prove that proposal number n has value v under the additional assumption that every proposal issued with a number in m . . (n − 1) has value v , where i . . j denotes the set of numbers from i through j . For the proposal numbered m to be chosen, there must be some set C consisting of a majority of acceptors such that every acceptor in C accepted it. Combining this with the induction assumption, the hypothesis that m is chosen implies:
Every acceptor in C has accepted a proposal with number in m ..(n − 1), and every proposal with number in m ..(n − 1) accepted by any acceptor has value v
So the induction process is:
- Base case: proposal m with value v has been chosen
- Inductive step: any proposal in number m ..(n-1) have value v
Why it implies that:
Every acceptor in C has accepted a proposal with number in m ..(n − 1)
I just can't bridge the gap, why does every acceptor in C need to accepted a proposal with number in m..(n-1)?
P1 guarantees that acceptor must accept the first proposal received, P2a guarantees that only the higher-numbered proposals with the chosen value could be accepted by acceptors, but I just don't get the point of the implied statement.