Notes on consensus algorithms

Consensus algorithms allow a set of nodes to agree on a value despite failures. In this post I review the key concepts of Raft and Paxos.

Raft

Raft splits the problem into three subproblems:

1. Leader election: one node is elected leader and handles requests.
2. Log replication: the leader replicates its log to followers.
3. Safety: if a node has applied an entry at an index, no other node will apply a different entry at that index.

Election is by random timeout; the first to timeout starts a vote.

Paxos

Paxos is more abstract and is formulated as proposals (proposal number + value). A proposal is chosen when a majority accepts it. The details are subtle to avoid livelock and ensure progress.

References

• In Search of an Understandable Consensus Algorithm (Ongaro, Ousterhout)
• Paxos Made Simple (Lamport)