The protocol guarantees that all values learned by all learners must be equal. To see this, consider two proposals P and Q whose values have been learned by any of the learners (not necessarily the same one):
This is a proof by contradiction, so suppose that the protocol was incorrect and that the values learned were different:
Then the values proposed were also different:
Now consider also the proposals that have been made (or will ever be made) between P and Q:
Find the earliest proposal R later than P but no later than Q whose value is not X:
Put differently, all the ones earlier than R but no earlier than P have value X:
The value of P must have been learned because it was accepted by a majority
S of acceptors, and the value for R was proposed because of promises from
another majority of acceptors which therefore overlaps S. Pick one of the
acceptors in the overlap, say alice, who accepted P and then promised to
accept R. It must have happened in that order as, having promised to accept
R, alice would then not have been able to accept P.
Of course alice may also have accepted some proposals later than P before
promising to accept R. In any case, the highest-numbered one accepted by
alice has value X as it is no earlier than P and is strictly earlier
than R.
Therefore when alice promised to accept R, the promise must have included a
lastAcceptedTimePeriod that is no earlier than P and is strictly earlier
than R, and the lastAcceptedValue is X. The other promises may also
have included a lastAcceptedTimePeriod, all of which are strictly less than
R:
In any case, the value proposed for R must be the lastAcceptedValue of the
promise with greatest lastAcceptedTimePeriod, which must be X as it is no
earlier than P and strictly earlier than R. This means that R didn't have
a different value from P, which is a contradiction. Therefore the original
assumption that P and Q had different values was wrong, and hence any two
learned values must be equal.