Does the Paxos algorithm use failure detectors?

Question

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

Answer 1

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".