Paxos Made Simpler

Paper reading: Paxos Made Simpler

Paxos comes up often while talking about distributed systems. A number of interesting papers refer it. I finally got an opportunity to read the Paxos paper. Here’s my attempt to make sense of it:

The problem statement:

Paxos algorithm proposes a solution to the consensus problem encountered in distributed systems.

Briefly described: how can a number of nodes in a distributed network arrive at a consensus regarding a value? This is important for nodes to have a consistent view of the data. For example: imagine you deposited $1000 in your bank account. The data is stored on multiple machines and they all need agree to increase your balance by $1000.

And this is difficult to ensure because:

Solution proposed:

Paxos splits the nodes into three groups and they work in two phases or arrive at consensus.

There are three groups of nodes -

In practice, one node can belong to multiple groups.

The proposals are put forward to the acceptors, by the proposers, in the form of requests. These can be of two types:

The algorithm works in two phases:

A value is chosen by the Paxos algorithm when a learner discovers that a majority of acceptors have accepted a value.

This is the basic algorithm. The paper goes into some detail describing the correctness of the algorithm.

References and related reading:

Site Reliability Engineer@Twitter

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store