Paxos and Raft

Learn about the Paxos and Raft consensus protocols.

We'll cover the following

Basic Paxos

Paxos is a family of consensus algorithms that work in a distributed system. The Paxos algorithm was developed by Leslie Lamport and published in his 1998 paper, “The Part-Time Parliament.”

The host proposing a value is a proposer and the host accepting the proposal is an acceptor. Basic Paxos is the most basic consensus algorithm of the Paxos family. Basic Paxos has two phases, Phase 1 and Phase 2.

Phase 1

Phase 1 also has two subphases:

  • Prepare

  • Promise

In the prepare phase, the proposer creates a Prepare message with a number X, which is a unique identifier of the message and greater than any of the previous Prepare messages from that proposer. Now, the proposer sends this message to a Quorum of acceptor hosts.

Once the acceptor receives the message, there are two scenarios:

  • If X is greater than the previous message number accepted by the acceptor, the acceptor responds with a Promise message indicating no further proposals lesser than X will be accepted. If an acceptor has accepted a previous proposal W such that W < X, it returns W along with the promise message.

  • If X is less than the previous message number accepted by the acceptor, the acceptor ignores the message.

Phase 2

Phase 2 is the actual consensus phase for message exchange. Phase 2 has two subphases:

  • Accept

  • Accepted

Once the proposer receives a promise from a quorum of acceptor nodes, the acceptor decides on the proposed value. The proposer sends an Accept message in the format (X, v) to a quorum of acceptors where:

  • The number X is passed in the Prepare request.

  • The value v is either proposed by the proposer or is the value suggested by the acceptor if it is greater than the value proposed by the proposer.

In the accepted phase, once the acceptor receives the Accept message in the format (X, v):

  • It accepts it if it has not already promised to any Prepare requests greater than X.

  • Otherwise, it rejects the Accept request.

Once the acceptors send an Accepted request, it forwards the value learned to learners.

Get hands-on with 1200+ tech skills courses.