What guarantees Paxos to converge (terminate)? (i.e. not run forever without a consensus)

Question

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

Answer 1

There is no guarantee that Paxos will converge. In fact, more strongly, it can be shown that it is impossible to guarantee convergence of a distributed consensus algorithm in an asynchronous network. See for example Fischer, Lynch and Patterson's short paper ‘Impossibility of Distributed Consensus with One Faulty Process’.

In practical implementations it is usual to rely on the fact that, as long as enough nodes are working and communicating with each other, if exactly one node sends out a PREPARE (phase 1a) message for a sufficiently large ballot, and there are no other messages in flight, then the system will converge in a small number of round-trips. These conditions can be arranged, eventually-almost-certainly, by using randomised timeouts and maybe some kind of backoff.