4
$\begingroup$

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

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ The Paxos algorithm does not guarantee termination (or convergence in your term). In section 2.4 titled "Progress", Lamport has given a scenario in which two proposers each keep issuing a sequence of proposals with increasing numbers, none of which are ever chosen. $\endgroup$ – hengxin Mar 30 '14 at 12:59
  • 1
    $\begingroup$ Yes, that might be true, but I would still like to know how come Paxos terminates in practice. Is there some formal (maybe probabilistic) analysis that shows that the probability of not convergence is negligible? Or something similar. $\endgroup$ – Pinocchio Apr 30 '14 at 19:20
  • $\begingroup$ As @hengxin mentioned, Paxos does not (and cannot) converge. You should edit the question to focus on the probabilistic bounds that it has. $\endgroup$ – VF1 May 28 '14 at 23:14
  • $\begingroup$ @VF1 I have not read papers studying on the probabilistic analysis on Paxos. However, for the consensus problem, there are many randomized algorithms (e.g., Another advantage of free choice: Completely asynchronous agreement protocols). In the blog article, it says 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$ – hengxin May 29 '14 at 1:44
  • $\begingroup$ @hengxin I agree. Thanks for the links. $\endgroup$ – VF1 May 29 '14 at 2:07
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Is there any guarantee that Paxos will converge in a synchronous network? $\endgroup$ – lmaooooo Jan 6 '20 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.