how does Paxos Consensus algorithm behave in an asynchronous environment? Because as far as I know Paxos only work in synchronous environment. Correct me if I am wrong :)

Sorry for the noob question, started learning about Paxos yesterday only.


1 Answer 1


The basic Paxos protocol (that is, without leader election) is totally asynchronous. In Lamport's paper, the basic protocol is derived from a consistency lemma in section 2.2.

However, it does not guarantee progress (section 2):

A restricted version of the preliminary protocol provided the basic protocol that guaranteed consistency, but not progress.

(While not guaranteeing progress, the basic protocol never deadlocks. Progress is always possible but cannot be guaranteed in any finite amount of time)

In fact, the FLP Impossibility Result tells us that no asynchronous protocol can guarantee progress and be correct in the presence of failures.

Paxos adds a limited amount of dependence on time to choose presidents. If there is exactly one president that can communicate with enough nodes for enough time to complete the protocol, then progress is guaranteed.

However, having multiple presidents does not lead to inconsistency--it simply means that progress is not guaranteed.

However, in the Paxon Synod, having multiple presidents could only impede progress; it could not cause inconsistency. For the complete protocol to satisfy the progress condition, the method for choosing the president needed only to satisfy the following presidential selection requirement (section 2.4):

If no one entered or left the Chamber, then after T minutes exactly one priest in the Chamber would consider himself to be the president.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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