Distributed Systems Mastery: From Bakery Algorithm to Paxos, Lessons from Leslie Lamport
Table of Contents
TL;DR
- Understand how Lamport’s algorithms keep many computers in sync.
- Learn why mutual exclusion matters in concurrent programs.
- See how state-machine reasoning can simplify complex protocols.
- Discover the practical trade-offs between Paxos, Raft, and Byzantine fault tolerance.
- Get actionable tips on writing clear proofs and documentation.
Why this matters
When you build a system that runs on dozens of machines, a single mis-ordered message can crash the whole thing. Every engineer I’ve worked with once ran into a subtle race that only appeared under heavy load. The pain points I’ve seen time and again are: ensuring mutual exclusion in concurrent programs, avoiding starvation in algorithms, debugging subtle bugs in distributed protocols, and maintaining consistency across replicas. These problems are the bread and butter of distributed systems, and they’re the problems that Leslie Lamport set out to solve. By studying his career, you get a blueprint for how to think about these problems and how to design algorithms that actually work in the real world. Lamport is a Turing Award winner, known for imposing clear, well-defined coherence on distributed systems Leslie Lamport — Wikipedia (2026).
Core concepts
Lamport’s work can be divided into three pillars:
| Parameter | Use Case | Limitation |
|---|---|---|
| Bakery Algorithm | Mutual exclusion for a few processes with shared memory | Requires two processes and relies on shared memory; not suited for networks with message loss |
| Paxos | Consensus in an asynchronous network of unreliable nodes | Requires a majority (2f + 1) nodes for f failures; complex to implement |
| Raft | Simplified consensus with a clear leader and log replication | Not Byzantine-fault tolerant; originally had a subtle bug that was later fixed |
Bakery Algorithm
The bakery algorithm is Lamport’s elegant solution to the classic “only one process in the critical section” problem. Picture a bakery counter where each customer draws a number on a ticket machine. The tickets are strictly ordered, so the customer with the lowest number gets served next. Lamport translated this idea to concurrent threads: each thread writes a ticket number into a shared array and then waits for its turn. The algorithm is first-come-first-served, uses only simple reads and writes, and crucially does not need atomic operations on shared memory. This makes it portable even to hardware that doesn’t support atomic primitives. The proof of correctness relies on invariants—simple statements that remain true no matter how the processes interleave. The entire proof is remarkably short, which is why Lamport said that “the bakery algorithm’s proof was simple” and that it “used invariants for correctness” Bakery Algorithm — Wikipedia (2026). The bakery algorithm’s proof was simple Bakery Algorithm — Wikipedia (2026), and it uses a ticket system inspired by a deli counter Bakery Algorithm — Wikipedia (2026). It also does not require atomic actions, making it robust on platforms without hardware support for atomic primitives Jeffrey Emanuel — Bakery Algorithm: Concurrency without Atomicity (2024).
Paxos
When you need agreement among a cluster of machines that can fail, you turn to Paxos. Lamport introduced Paxos in 1989, and the algorithm guarantees that all non-faulty nodes agree on the same value, even if messages are delayed or lost. The algorithm is built around two phases: prepare and accept. A key fact is that to tolerate f failures you need at least 2f + 1 processes; for a single fault that means four processes if you don’t use digital signatures, or just three if you do Paxos — Wikipedia (2026). The rule comes from the requirement that a majority of honest nodes must be able to form a quorum. The original Paxos paper is notoriously hard to read, so Lamport later wrote “Paxos Made Simple” (2001) to strip away Greek jargon and explain the core idea in plain English. The Microsoft page for that paper is a primary source and is still used as a reference in academic courses Microsoft — Paxos Made Simple (2001).
Raft
Raft was introduced by Diego Ongaro and John Ousterhout in 2014 as a consensus algorithm that is easier to understand than Paxos. Raft divides the protocol into three parts: leader election, log replication, and safety. It uses a clear leader, which makes the algorithm more intuitive. Raft’s original design had a subtle bug in the log replication phase that caused inconsistencies under a very specific set of circumstances. The bug was discovered and corrected in a subsequent revision, and the corrected version is now the de-facto standard in many production systems. The bug is documented in the Raft Wikipedia article, which is a good quick reference for the timeline of the bug and its fix Raft — Wikipedia (2026).
How to apply it
Start with a clear description
Lamport always said that you should write a description before you write any code. The act of writing forces you to clarify the problem, the assumptions, and the invariants. In a recent interview, Lamport reminded his younger self that “writing a description before coding helps clarify thinking” Developing.dev — Interview with Leslie Lamport (2026).Choose the right algorithm for the job
- If you have a small set of shared-memory processes that need mutual exclusion, try the bakery algorithm. It needs only two processes and works even when atomic operations aren’t available.
- If you’re building a distributed database that can lose nodes but still needs agreement, Paxos is the gold standard. Remember the 2f + 1 rule: for one fault you need four nodes unless you add digital signatures, in which case three nodes suffice.
- If you want a leader-based system that is easier to understand, Raft is a good choice. But keep an eye on the log replication phase and test for the known bug conditions.
Model your system as a state machine
Lamport called the state machine a “Turing machine of concurrency.” Think of each node as a tiny computer that has a state and a next-state relation. The state machine abstraction lets you reason about safety properties—like “no two nodes ever see the same log entry at the same time”—without getting lost in the details of message passing.Write invariants and proofs
Even if you’re not a formal methods expert, writing a few key invariants (e.g., “the log index never decreases”) can catch subtle bugs early. Lamport’s own proofs are hierarchical: you prove small lemmas, then use them to prove the main theorem. The bakery algorithm’s proof is a great example of how a short invariant can guarantee safety.Test for starvation and failure scenarios
Dijkstra’s original solution suffered from starvation. Lamport’s bakery algorithm fixes that by using a ticket system. When you test, make sure you simulate high contention and node failures. For Paxos, test scenarios where a majority of nodes drop a message. For Raft, test the leader election under network partitions.Document everything
Lamport’s own LaTeX macro package was a testament to his belief that clear documentation matters. He built LaTeX to give authors macro extensibility LaTeX — Wikipedia (2026). The same philosophy applies to algorithm documentation: write a high-level description, then document the invariants, then provide a simple proof sketch.
Pitfalls & edge cases
- Starvation in classic mutual exclusion: Dijkstra’s original algorithm could starve a process if it repeatedly missed its turn. Lamport’s bakery algorithm fixes that by using a ticket system.
- Paxos process count: A common mistake is to assume “three nodes are enough” for one fault. That is only true if you employ digital signatures. Without them you need four nodes. Forgetting this leads to a fragile cluster.
- Raft bug: The original Raft implementation had a corner-case bug in the log replication phase that could cause a follower to accept an inconsistent log entry. The fix added a safety check on the last log term. If you are using Raft, make sure you’re on the latest version.
- Byzantine actors: The Byzantine generals problem formalizes how malicious nodes can subvert consensus. Lamport’s work on digital signatures shows that adding signatures can reduce the process count from 3f + 1 to f + 1. However, this adds cryptographic overhead and requires a secure key distribution mechanism.
- Shared memory limitations: The bakery algorithm assumes that all processes share a memory region. In a networked environment you would need a distributed shared-memory layer, which is rarely available.
Quick FAQ
| Q | A |
|---|---|
| What is mutual exclusion and why is it important? | Mutual exclusion ensures that only one process can execute a critical section at a time, preventing data corruption when multiple processes access shared resources. |
| How does the bakery algorithm guarantee fairness? | It assigns a ticket number to each process and serves them in ascending order, guaranteeing first-come-first-served fairness. |
| Why does Paxos require 2f + 1 processes for f failures? | A majority of honest nodes must be able to form a quorum to agree on a value; the math works out to 2f + 1. |
| How do digital signatures reduce Paxos’ process count? | Signatures allow nodes to verify authenticity of messages, enabling a lower quorum size (f + 1) while still guaranteeing safety. |
| What was the bug in Raft and how was it fixed? | The bug involved an inconsistent log entry being accepted during replication; the fix added a safety check on the last log term. |
| How can I adapt the bakery algorithm for modern multi-core processors? | Use a lock-free ticketing mechanism and avoid shared memory by using per-core ticket registers, then combine with a memory-barrier to maintain order. |
| What lessons can I apply from Lamport’s approach to blockchain? | Treat the blockchain as a state machine, write invariants, and document the protocol clearly—exactly how Lamport advocated for distributed systems. |
Conclusion
Lamport’s career shows that the hardest distributed systems problems can be solved with clear thinking, rigorous proofs, and good documentation. The bakery algorithm, Paxos, and Raft are more than academic curiosities; they are practical tools that you can adapt to your own systems. Start by writing a description of the problem, choose the right algorithm, model your system as a state machine, write invariants, test for edge cases, and document everything. If you keep these steps in mind, you’ll reduce bugs, avoid starvation, and build systems that stay consistent even when the world is unreliable.
