Paxos Made Simple

TLDR

Paxos is often perceived as complex, yet its core logic is straightforward. The paper’s goal is to demystify Paxos by offering a concise, paperless explanation. The authors orally presented the algorithm to peers, then distilled it into a 13‑page note refined with input from Fred Schneider and Butler Lampson. The final note uses only simple inequalities such as n₁ > n₂, underscoring the algorithm’s simplicity.

Abstract

At the PODC 2001 conference, I got tired of everyone saying how difficult it was to understand the Paxos algorithm, published in [122]. Although people got so hung up in the pseudo-Greek names that they found the paper hard to understand, the algorithm itself is very simple. So, I cornered a couple of people at the conference and explained the algorithm to them orally, with no paper. When I got home, I wrote down the explanation as a short note, which I later revised based on comments from Fred Schneider and Butler Lampson. The current version is 13 pages long, and contains no formula more complicated than n1 > n2.