Skip to main content

Paxos and RAFT

· 2 min read
Sanjeev Sarda
Sanjeev Sarda
High Performance Developer

What are Paxos and RAFT?

paxos and raft

Paxos and RAFT​

Paxos and RAFT are two families of algorithms for providing consensus in distributed computing.

Fundamentally, the difference in the approach is that Paxos uses p2p consensus and RAFT uses a single leader, multi-follower mechanism. There are just a few more steps in Paxos and a different messaging flow.

RAFT​

  • Elections are triggered on the failure of an existing leader - this can be via heartbeat timeout for example

  • A new leader triggers the start of a new term

  • In RAFT the leader is responsible for log replication after local persistence

  • Once the leader receives acks from >50% of the peers, it can apply the event or action to it's own state machine (leader commit)

  • Once the leader has committed, peers also commit by applying the event to their local state machine

alt text

Source: Container Solutions

Paxos​

Paxos has developed into a family of algorithms that build upon the original Paxos implementation to provide other features like handling Byzantine failures.

Uses the idea of sequenced proposals from multiple proposers (prepare request messages) and a number of acceptor agents (which can send back prepare response messages).

Requires quorum on prepare-response messages from acceptor agents at the proposer.

Once the proposer has determined quorum, it sends an accept message to the acceptor agents. The acceptor agents can then broadcast out the accepted new value to any learner agents.

alt text

Source: Lu Pan's Blog (Distributed Engineer at FB)

Byzantine Failures​

This is a class of failure that includes things like lying, fabrication of messages, collusion with other participants, selective non-participation etc.

It also includes things like sending inconsistent state to different peers e.g. saying a service is up to one peer whilst telling a different peer the service is down.

Paxos Made Simple, 2001 - Leslie Lamport

Raft Algorithm - Wikipedia

Paxos Consensus - Wikipedia