So that's the Paxos protocol in a nutshell fairly simplified here.
'kay.
Now the question here is what is the point in order.
When has consensus already been reached in the system?
You might think that consensus has been reached when
the Law phase is done at the end of the final value being multicast but in fact,
consensus is reached slightly earlier even though the processes don't know it yet.
In fact, consensus is reached in the middle of the Bill phase,
when the majority of processes have heared, have heard of the propo,
proposed value and have logged it.
They may not have responded to it with an OK but
because they have logged it, they would start where they left off, and
that would eventually, lead to a majority of OKs.
The processes may not know it yet, but a decision has been made for the group.
And even a leader may not know it yet, and
that's the point of no return after which that value will be decided in the future,
and no other value will be decided in the future.
If the leader fails after that, you simply restart the round, and
processes will then respond back with the old decided value v in this case,
which the leader is then forced to use in the Bill phase.
Because that's what we discussed earlier the leader has to do.
So, why does this algorithm guarantee safety?
In other words, why does it ensure that two different values are not decided by
two different processes?
Well, if some round has a majority, that is a quorum, hearing proposed value v
prime and accepting it in the middle of Phase 2, then subsequently at each round
either the round chooses v prime as its decision, or the round fails.
In other words, either it obeys safety, or it just starts another round.
Okay? So it doesn't
decide any other value other than v prime.
Well, the reason for this seeing through is that potential leader waits for
a majority OKs in Phase 1, and because this is a majority or quorum, and
a quorum has already heard a proposed value v prime.
That quorum that the leader waits for, and
the quorum that has accepted v prime will intersect in at least one process.
And that process will send the value of v prime to the potential leader, and
the potential leader will be forced to use that value v prime for the Bill phase.
And so if the round ever makes a decision, it will be the value of v prime.
The round might, however, fail and in that case the round will just restart again,
a new round will start, and in that case, again, the value v prime will be used
in the Bill phase for the same reasons as we have just talked about.
So the key here again, is that success requires a majority or a quorum, and
any two majority sets or quorums intersect in this particular case.