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 aPromise
message indicating no further proposals lesser thanX
will be accepted. If an acceptor has accepted a previous proposalW
such thatW
<X
, it returnsW
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 thePrepare
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 thanX
.Otherwise, it rejects the
Accept
request.
Once the acceptors send an Accepted
request, it forwards the value learned to learners.
Get hands-on with 1400+ tech skills courses.