I was studying Paxos from:
Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.
I was reading page 4 of the paper where it says condition $P2^c$:
"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."
(Where S = any set consisting of a majority of acceptors. C = the set of acceptors that have accepted some value c, the letter C stands for the majority that has Chosen a value).
I was trying to understand better the conditions for issuing a proposal, specifically (b) is the one causing troubles for me.
For me (a), makes sense because we don't want to issue a new proposal with a higher sequence number if there has been any proposal that has been chosen from the majority we are able to see (i.e. S). Since anything that has been chosen is accepted and since something chosen is part of the majority C, if we issue a new proposal, we could risk confusing the current paxos instance when its already chosen a value.
However, (b) is less clear to me why we want it to hold. Recall (b) is:
(b) = "v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S".
Why are we interested in having that condition? Which safety properties does that condition help us maintain?
Author: Leslie Lamport
Title: Paxos made simple
Institution: Microsoft Research