We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
This idea carries a full system design question on its own. Each walks through the full answer.
System Design Masterclass · Distributed Systems Core
Free preview: the first 2 parts of this 11-part lesson.
Already bought the course? Sign in to read the whole lesson.
this lesson is part of
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design courseread the rest of this lesson in
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design coursein Distributed Systems Core
This lesson is part of the full System Design Masterclass. Unlock it along with 769 other lessons for a one-time payment.
One-time payment by card or PayPal
Get Lifetime AccessOne-time payment: UPI, card or netbanking
Get Lifetime Access18 Foundation lessons are free, no payment needed. Try them now
Leslie Lamport won the Turing Award in 2013, largely for his work on distributed , specifically, the Paxos algorithm. The problem Paxos solves sounds simple: how do a group of computers agree on a single value, even if some of them crash?
It doesn't sound hard until you think about what "agree" means in a world where messages get lost, reordered, duplicated, and delayed. Where any node can crash at any moment. Where you can't tell the difference between a crashed node and a slow one. Under these conditions, getting nodes to reliably agree on anything is one of the hardest problems in computer science.
The FLP impossibility result (Fischer, Lynch, Paterson, 1985) proved that deterministic consensus is impossible in an asynchronous system where even one node can crash. That's a mathematical impossibility, not "really hard" but "provably impossible." Every practical consensus algorithm (Paxos, , ZAB) works around this by using timeouts, randomization, or other mechanisms that break the strict asynchrony assumption.
Consensus is the foundation of every strongly consistent distributed system you've ever used. Etcd (which runs Kubernetes) uses Raft. ZooKeeper (which runs , HBase, and Hadoop) uses ZAB. Google Spanner uses Multi-Paxos. CockroachDB uses Raft. When these systems claim to be "strongly consistent," what they mean is "we run a consensus algorithm internally."
A algorithm must satisfy three properties:
Agreement. All non-faulty nodes decide on the same value. If node A decides "42" and node B decides "43," consensus has failed.
Validity. The decided value must have been proposed by some node. The algorithm can't just make up values.
Termination. All non-faulty nodes eventually decide. The algorithm can't run forever without reaching a conclusion (this is the property the FLP result shows is impossible to guarantee in all cases).
| Algorithm | Year | Creator | Used By |
|---|---|---|---|
| 1989 (published 1998) | Leslie Lamport | Google Spanner, Amazon internal | |
| Multi-Paxos | Extension of Paxos | Lamport | Google Chubby, Megastore |
| 2014 | Diego Ongaro | etcd, CockroachDB, TiKV, Consul | |
| ZAB | 2011 | Yahoo Research | Apache ZooKeeper |
| Viewstamped | 1988 | Oki, Liskov | Academic, inspired Raft |
| PBFT | 1999 | Castro, Liskov | Hyperledger, some blockchains |
Paxos is the original, proven correct, and notoriously difficult to understand. Lamport's first paper was written as a story about a fictional Greek parliament, which confused reviewers so much it went unpublished for years.
Raft was explicitly designed to be understandable. Diego Ongaro's PhD thesis was titled "Consensus: Bridging Theory and Practice" and the Raft paper was structured around pedagogy. The algorithm provides the same guarantees as Multi-Paxos but is dramatically easier to implement correctly.
It is easy and good
“It is really nice and good Please join the course”