Lamport's Bakery Algorithm

Picture a busy bakery. You walk in, pull a paper ticket from a dispenser, and wait. When the clerk calls your number, you step up — and nobody else cuts in front. The line is fair, orderly, and managed without a bouncer at the door.

In 1974, Leslie Lamport used exactly this metaphor to solve one of the oldest puzzles in computer science: how can multiple threads share a single resource — a file, a counter, a device — without ever colliding, using nothing but plain memory reads and writes?

The puzzle is called the mutual exclusion problem. It was first stated formally by Edsger Dijkstra in 1965, and it has three requirements:

• Mutual exclusion: at most one thread is inside the critical section at any moment.
• Progress: if no thread is in the critical section, one of the waiting threads eventually gets in.
• Bounded waiting: no thread waits forever — every request is eventually served.

Hardware designers solved the problem quickly with special atomic instructions like test-and-set or compare-and-swap, but Lamport asked a deeper question: can you guarantee mutual exclusion using only ordinary reads and writes, even on a machine that might reorder or overlap them? The bakery algorithm proved you can — and the proof is elegant enough to teach to undergraduates fifty years later.

Below, four threads compete for a critical section. Click Step to advance one thread at a time, or Run to let them race. Each thread picks the next ticket number, waits until it holds the smallest ticket, then enters alone.

<p class="hint">{{hint}}</p>
<div id="threads-row"></div>
<div id="cs-box">
  <span id="cs-label">{{cs_label}}</span>
  <span id="cs-occupant">{{empty}}</span>
</div>
<div class="log-wrap"><div id="log"></div></div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run"  type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
#threads-row { display: flex; gap: 8px; margin-bottom: 10px; flex-wrap: wrap; }
.thread-card {
  width: 96px; border-radius: 10px; padding: 8px 6px; text-align: center;
  border: 2px solid #c6cdd5; background: #f1f4f7; transition: all .25s;
  font-size: .8rem; line-height: 1.6;
}
.thread-card .tid { font-weight: 700; font-size: 1rem; }
.thread-card .ticket { color: #1d3557; font-size: 1.1rem; font-weight: 700; }
.thread-card .phase { color: #666; font-size: .72rem; }
.thread-card.choosing { border-color: #f4a261; background: #fff4ec; }
.thread-card.waiting  { border-color: #457b9d; background: #e8f0f7; }
.thread-card.inside   { border-color: #2a9d8f; background: #e4f5f3; }
.thread-card.done     { border-color: #aaa; background: #f7f7f7; opacity: .6; }
#cs-box {
  display: flex; align-items: center; gap: 14px;
  border: 2px dashed #2a9d8f; border-radius: 10px;
  padding: 10px 14px; margin-bottom: 10px;
}
#cs-label { font-size: .8rem; color: #555; }
#cs-occupant { font-weight: 700; font-size: 1.1rem; color: #1d3557; }
#cs-occupant.occupied { color: #2a9d8f; }
.log-wrap { height: 110px; overflow-y: auto; background: #f8fafc;
            border: 1px solid #dde3ea; border-radius: 8px; padding: 6px 8px;
            margin-bottom: 10px; font-size: .78rem; line-height: 1.6; }
#log p { margin: 0; color: #444; }
#log p.hi { color: #1d3557; font-weight: 600; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .42rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }

// Code not found

Notice: no thread skips the queue. When two threads grab tickets at the same moment they might get the same number — the algorithm breaks the tie by thread ID. Even with ties, exactly one thread enters the critical section at any instant, and every thread eventually gets its turn.

The algorithm's correctness relies on two properties that Lamport proved in his original 1974 paper:

• Mutual exclusion holds because before entering the critical section, thread i checks every other thread j: "does j hold a smaller ticket, or the same ticket with a smaller ID?" If yes, i waits. Only when i has the globally smallest (ticket, ID) pair does it proceed — and at that moment no other thread can also have the globally smallest pair.
• Bounded waiting holds because ticket numbers are assigned in increasing order. Once thread i has a ticket, every thread that later picks a ticket gets a larger number, so they cannot jump the queue.

What it costs. The algorithm uses 2n shared variables for n threads (a choosing flag and a number for each). Reading them all before entering takes $O(*n*)$ time — linear in the number of threads. Atomic hardware instructions achieve mutual exclusion in $O(1)$, so the bakery algorithm is theoretically slower, though in practice n is small.

The unbounded-number problem. Ticket numbers grow monotonically. In a system that runs forever, they eventually overflow any fixed-size integer. Lamport acknowledged this; in practice engineers either bound the run time or reset numbers safely between rounds.

Memory model subtlety. The correctness proof assumes sequential consistency — that reads and writes appear to happen in some global order. Modern CPUs violate this for speed. Real implementations need memory fences or compiler barriers to restore the necessary ordering. This is why, despite its elegance, the bakery algorithm is more often a teaching tool than a production primitive — hardware atomics are both faster and easier to use correctly. For a deeper look at the boundaries of what algorithms can do, see P vs NP and the halting problem.

The bakery algorithm is primarily a theoretical landmark, but its ideas permeate real systems:

• Operating system kernels: early spin-lock designs borrowed the ticket metaphor directly. Linux's ticket spinlock is a direct descendant — each CPU core takes a ticket and waits until the "now serving" counter reaches it.
• Distributed systems: Lamport extended the same idea to clocks. His logical clocks (also 1978) assign sequence numbers to events across machines, establishing a consistent global ordering — the same "take a number, serve in order" insight applied to distributed logs.
• Database locking: serializable transaction isolation requires that conflicting transactions appear to run in some serial order. Ticket-based ordering is one way schedulers enforce that requirement.
• Formal verification: the bakery algorithm is a standard benchmark for model checkers and theorem provers. Its small size and known properties make it ideal for testing whether a verification tool actually works.
• Teaching concurrency: because the algorithm requires no special primitives, students can implement it in any language on any machine and observe real race conditions — something impossible with opaque atomic hardware instructions.

The broader lesson is that ordering is the key to coordination. Whenever multiple agents need to take turns, the pattern is the same: assign a number, compare numbers, serve the smallest. That idea appears in everything from network packet sequencing to auction theory.

Lamport's bakery algorithm is fifty years old, and it still appears in the first chapter of every serious concurrency textbook. Its genius is not efficiency — hardware atomics beat it handily — but provability. Starting from nothing but reads and writes, Lamport constructed a watertight argument that threads can take turns fairly, and he wrote it down in a form anyone can check.

That matters for the same reason that a clean mathematical proof matters: it tells you exactly what the algorithm needs to work (sequential consistency), exactly what it guarantees (mutual exclusion, progress, bounded waiting), and exactly where it would break (overflow, reordering). Those precise boundaries are what let engineers build on top of it confidently.

The next time you grab a mutex, acquire a spinlock, or wait for a database transaction to commit, somewhere underneath that abstraction is the same insight Leslie Lamport had watching people wait their turn at a bakery counter: assign a number, wait for yours to be called, and the crowd sorts itself out.