The Paxos consensus protocol was introduced by Leslie Lamport in 1998, with a goal of overcoming the limits of the 2PC and 3PC protocols. When most of participants in a system are present and the delays in messages are minimal, in such cases the system is not blocked.

It is composed of three main actors, as follows:

• Proposer: This component has the responsibility to initiate the protocol. It proposes, as name says, the possible values of which the client wants the entire system to agree on. It send a proposal number to the acceptors and it waits for a response from a majority of them. In case most of the acceptors agree, the value of any previously accepted proposal will be returned; if the majority reply with reject, or fail to reply, they abandon the proposal and start again.
• Acceptor: This component responds to the proposal performed by the proposer. All of the nodes that participate in the transaction are required to know the quorum of acceptors that form a majority. Once the acceptor receives a proposal, it compares its value to the highest value proposal that the client has already accepted. If the new proposal is higher, it replies agree; otherwise, it replies reject.
• Learner: This component is responsible to learn which value was chosen by the acceptors in the consensus phase.

The protocol is based on two phases, as follows:

• Promise phase: In this phase, the proposer proposes a value on which to establish a consensus. Then, it communicates this value to all of the acceptors (or to the quorum) using a unique identification number generated from a sequence. The acceptor receives the proposed value and checks if it is higher than the last ID that the client has already agreed to. If this evaluation returns true, the acceptors will respond to the proposer with a promise message; otherwise, no action will be taken.
• Commit phase: In this phase, the proposer collects all the answers it received by the acceptors. If the majority answered with a promise, the proposer sends them an accept-request. The majority of acceptors reply with an accept message to the proposer and learners that finally accept it. In this way, all the members involved in a distributed environment reach the consensus and decide to commit the transaction. Otherwise, a rollback operation will be performed.

Paxos was the first protocol that was resilient in asynchronous networks; it prefers to sacrifice liveness when the network is behaving asynchronously rather than correctness. It terminates the operations only when synchronicity returns.

In spite of this, it has some issues; the concurrency competition of two proposers trying to obtain the highest proposal number can cause the system to be blocked until the conflict is resolved.

The consensus is a very sophisticated and complex problem; at the time of writing this book, in the Java EE/Jakarta EE environment, the most commonly applied protocol is 2PC.