Does the Paxos algorithm use failure detectors? If not, how can it solve consensus, given the impossibility result?


In short, the "plain" Paxos algorithm does not use failure detectors, but it can be augmented with failure detectors. Furthermore, the "plain" Paxos algorithm does not fully solve the problem of consensus.

To answer this question more in detail, we first define "the consensus problem". An algorithm "solves" the problem of consensus if it guarantees that the following properties are satisfied:

  • Termination (or liveness, or progress): all non-faulty processes eventually decide on a value
  • Agreement (or consistency, or safety): all processes that decide do so on the same value
  • Validity (or non-triviality): the value that has been decided must have proposed by some process

The "plain" Paxos guarantees that agreement and validity are always satisfied, that is, if you use Paxos to solve consensus, then you will never get as a result processes that decide on different values or that decide on values that have never been proposed.

However, "plain" Paxos does not guarantee termination, that is, if you use "plain" Paxos, then it is possible that processes will never decide on a value. This problem can be (partially) circumvented by using using "leader election", that is, you elect a leader (which must be a proposer in the "plain" Paxos algorithm) which coordinates the proposals. However, the leader can also fail. This failure of the leader can e.g. be detected using failure detectors (which, in practice, may be implemented as "timeouts"). Therefore, Paxos can use failure detectors. But I won't dwell more on this topic.

In conclusion, "plain" Paxos does not fully solve the problem of consensus, because it does not guarantee "progress".

| cite | improve this answer | |
  • $\begingroup$ Note that the FLP impossibility result says that no protocol can solve the consensus problem in an asynchronous environment, even in the presence of just one crash-fault. $\endgroup$ – Curtis F Jan 15 '19 at 1:36
  • $\begingroup$ @CurtisF Yes, but this is a general and theoretical result, that is, there is no algorithm which solves consensus in all possible cases. $\endgroup$ – nbro Jan 15 '19 at 10:46

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.