Paxos Made Simple: Demystifying the Complex Distributed Consensus Algorithm
Paxos Made Simple (2001)[pdf]
I argue that the Paxos algorithm is actually one of the simplest distributed algorithms, despite its reputation for difficulty. By breaking down the consensus problem into clear roles for proposers, acceptors, and learners, I show how a single value can be chosen reliably even in asynchronous systems with failures. This straightforward approach forms the foundation for building robust, fault-tolerant state machines.
The Paxos algorithm for implementing a fault-tolerant distributed system has been regarded as difficult to understand, perhaps because the original presentation was Greek to many readers.
- projectileboy
More enjoyable to read this within a broader context: https://pdos.csail.mit.edu/6.824/
- pss314
"Paxos Simplified" (video & slides below) attempts to give a simple and clear explanation of Paxos. It is inspired by Leslie Lamport's paper "Paxos Made Simple".
- L9: Paxos Simplified https://www.youtube.com/watch?v=SRsK-ZXTeZ0
- Slides https://docs.google.com/presentation/d/1ossDCdSERSZmJXKfiCwD...
Check out https://www.distributedsystemscourse.com/ by Chris Colohan for more info.
- arionmiles
When I first started reading seminal works in Distributed Computing, I picked up the original (The Part-time Parliament) and it started off pretty well with the made up story of finding the algorithm as a manuscript from an archeological dig.
The original paper then quickly becomes super convoluted by continuing to explain the algorithm by overextending that allegory. By the mid point of it I felt pretty exhausted.
It was then I learnt that the original paper was lying in limbo for nearly a decade until it was finally published.
Then at a conference, Lamport got tired of people telling him his original was difficult to grasp and so came this simplified explanation.
I still have my notes on the paper somewhere in my Obsidian. I should publish those.