I was studying Paxos from:
http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf
and was wondering, what guarantees Paxos to converge and not run forever without a consensus/agreement on a value? Is it guaranteed to converge always or is it a probabilistic bound that the probability that it does not converge is really really small?
Because I was reading condition $P2^c$ and it seems possible to me that because of that condition, Paxos might loop forever if we are not careful (I think, maybe I am wrong, but I would love to know why!) Take the following case:
I was a little worried about the case when, say that a majority was close to forming but there is a new node that wants to propose his new value but was unlucky and did not happen to communicate with that growing set that nearly formed a majority (its not a majority yet, but it was reaalllyyy close!). That node was ready to prepare his value but was that unlucky and reasoned "Ok, none of the nodes I spoke to had a value, thus, time to propose my value!" but his sequence number is much higher than the previous one that was forming on the other side and it starts to spread, wouldn't it be because we want to satisfy (b) in $P2^c$? i.e. doesn't it damage the convergence to a decision (never mind the run time, it might never converge...)? Even in the case of a very good quality network..?
Because now this new node has a higher value and his value spreads like a disease and it could happen again, right before it was about to form a majority with his own value. That situation could happen again and again and again no value is decided! Right? What prevents Paxos from being in this situation? Or what is the argument to convince me that its really unlikely to happen many times and that it converges in polynomial time most of the time?
Recall condition $P2^c$ is the following:
$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."
Author: Leslie Lamport
Title: Paxos made simple
Institution: Microsoft Research
The number of rounds and it's Byzantine fault tolerant counterpart, is surprisingly low. For many executions, consensus can be reached on the first round ...
. I think it would be interesting to do the probabilistic analysis on Paxos. $\endgroup$