Ruchit Singh
← All posts

Starbucks, Bakery Algorithm, and Lamport Shenanigans

How a Tuesday morning Starbucks queue explains Lamport's Bakery Algorithm, and where the same idea shows up in Kafka, Postgres, and Raft.

#systems-engineering #algorithms #concurrency

It’s Tuesday. 10AM. I’m standing in the Starbucks queue on Princes Street, half asleep, clutching my Unidays ID because today they’ve got tall drinks for two quid and there is absolutely no way I’m missing that! The place is packed. Almost everyone is a student. There are at least 6 people who look like they haven’t got rid of Monday’s blues. Some of them are ranting on their dissertation proposals:

Person A: “This proposal is doing my head in. What was I thinking when I chose this research angle?”
Person B: “Aye mate, I wish I could say the same! My prof is so sweet, he’s given me exact papers to do my groundwork on”

I go up to the barista, she’s pretty sweet. I have been collecting points like how genz collected pokemons back in the day. We chatter about new merchandise and drinks that’s in store today. Anyways, I show my ID, order the drink, step aside and within few mins “Ube Vanilla Latte for Ruchit!”. Did ya reckon it’s pronounced as ooo-be? I grab my coffee and head for a table.

I did not expect to be thinking about my PPLS exam that’s coming up in a week, but here we are.

Chaos! What’s that?

Look around that Starbucks on a Tuesday morning. There are maybe twenty people waiting. Two baristas. One espresso machine. Orders flying in from every direction. And yet: nobody gets two drinks. Nobody gets forgotten. Nobody’s oat milk latte mysteriously becomes someone else’s. The orders come out in roughly the right sequence, and the right person picks up the right drink.

How? Honestly, I didn’t think about it at first either. But somewhere between my second sip and opening my PPLS notes, it hit me: this is just a queue with tiebreaking. That’s it. That’s the whole thing Lamport spent a paper on.

The actual problem

In simple terms, like my Professor Murray Cole would explain(who is absolutely fantastic): Programs can run multiple threads at the same time. Most of the time that’s completely fine. But sometimes, shit goes sideways. Two threads end up touching the same piece of data at the same moment and in one of the most infuriating ways possible.

For example:

// Thread A                          // Thread B
read counter -> 100                  read counter -> 100
add 1                                add 1
write counter <- 101                 write counter <- 101

Both threads read 100. Both write 101. The expected answer was 102. One update just… vanished (exactly how she’d ghost you on Hinge). No error. No crash. Just silently wrong.

This is called a race condition. The bit of code where it happens is called Critical Section, a region only one thread should be in at a time. The question is how do you enforce it? Lamport solved it by giving us what’s called the Bakery Algorithm.

Giving your name = signalling intent

When I walk up and say “Ube Vanilla latte, tall please”, the barista doesn’t just start making it immediately. They write my name on a cup and slot it into the sequence. I’ve registered my intent and joined the queue. In the algorithm, every thread does the same thing when it wants to enter the critical section:

turn[i] = 1                          // "I'm about to join the queue"
turn[i] = max(turn[1..n]) + 1        // "Here's my actual position"

First it sets its slot to 1, a signal that says “I’m in the process of joining, don’t ignore me.” Then it looks at everyone else’s current position, takes the highest number it sees, and adds one. That becomes its place in the queue.

Queue evolution

Here’s what that looks like in practice. Say there are 7 threads. At the start, nobody’s competing:

[0, 0, 0, 0, 0, 0, 0]
Thread 1 walks up and joins:
[1, 0, 0, 0, 0, 0, 0]
Thread 2 joins, sees Thread 1 is at position 1, takes 2:
[1, 2, 0, 0, 0, 0, 0]
A few more pile in:
[1, 2, 3, 4, 0, 0, 0]
Thread 1 gets served and leaves:
[0, 2, 3, 4, 0, 0, 0]
Thread 5 now joins, looks at the array, sees the highest is 4, takes 5:
[0, 2, 3, 4, 5, 0, 0]

Every thread can see this array at all times. That’s what makes the waiting loop work — when Thread 3 wants to know if it should wait for Thread 2, it just checks turn[2]. If it’s nonzero and lower, it waits.

Waiting your turn

Once I’ve given my name, I step aside. I don’t hover at the counter. I don’t keep asking “is mine ready?” every ten seconds. I wait until the orders ahead of me are done. The algorithm does the same:

for each other thread j:
    wait while (j is in the queue)
          AND (j's position beats mine)

“J’s position beats mine” means j has a lower number. You only step up, enter the critical section when you genuinely have the next position in line.

Two people named Alex: the tie problem

Here’s a scenario every busy Starbucks eventually produces. Two people order at almost exactly the same moment. The barista turns around, calls “Alex!”, and two people step forward. In the algorithm, the equivalent happens because looking up everyone’s current position and computing your own isn’t instantaneous. Two threads can read the same maximum simultaneously and both decide they’re position 7. A tie. The fix is a tiebreaker: when two threads have the same number, the one with the lower thread ID wins. Arbitrary, but perfectly consistent, like the barista saying “okay, you were slightly to my left, you go first” and sticking to that rule every single time.

// compare (ticket, thread_id) lexicographically
// lower ticket wins; equal tickets broken by lower thread ID

wait while (turn[j] != 0) AND (turn[j], j) < (turn[i], i)

No ambiguity. No standoff. Someone always goes first.

The cleverest bit: hand on the counter

This is the part that tripped me up when I first read it, and it’s the subtlest piece of the whole algorithm. Computing your position in the queue takes a small but nonzero amount of time. There’s a window between when you decide to join and when your number is actually written down, where your slot looks empty to everyone else.

Imagine this: you’re halfway through giving your order, the words are still coming out of your mouth, and the barista hasn’t written your name on a cup yet. Another student behind you glances at the cups lined up on the counter, sees nothing with your name on it, and thinks “oh, nobody’s waiting on this” and somehow jumps ahead. You’d lose it. And fairly so. That gap between you deciding to order and your name actually being on a cup is a real bug waiting to happen in a naive implementation.

The fix is the turn[i] = 1 line we saw earlier, setting your slot to 1 before computing your real number.

turn[i] = 1                          // "I'm at the counter, pen's in hand"
turn[i] = max(turn[1..n]) + 1        // "Okay, here's my actual number"

The 1 is your hand on the counter before the cup gets written. It tells every other thread: I am in the process of joining this queue, do not count me out. No real position is ever 1 because real positions are always max+1, and once anyone is active the max is at least 1, making the minimum real position 2. So 1 is unambiguously a sentinel, never a real queue position. When your name gets called and you grab your coffee, you’re done. You leave. The queue moves on.

turn[i] = 0     // "Got my coffee, I'm out"

Setting your slot back to zero tells everyone else you’re no longer competing. The next person in line steps up.

Does everyone eventually get served?

Yes. And this is the property that makes the Bakery Algorithm better than simpler approaches. With a naive spin lock (basically “keep hammering the door until it opens”) there’s no fairness guarantee. The scheduler could keep handing access to the same thread over and over, starving everyone else indefinitely. The Bakery Algorithm guarantees eventual entry. Because queue positions only increase, every waiting thread will eventually hold the lowest active number and will eventually get in. Nobody waits forever. The Tuesday morning Starbucks queue, however brutal it looks, is fair.

Putting it all together

So here’s the full algorithm, side by side. The barista’s version and Lamport’s version.

From the barista’s counter:

  1. Customer walks up and puts their hand on the counter (“I’m about to order”)
  2. Customer looks at all the cups in the queue, takes the highest number, adds one. That’s their position.
  3. Customer steps aside and waits. For every other person in the queue: if that person’s number is lower, or if it’s the same number but they were there first, wait.
  4. When it’s their turn, they get served (critical section).
  5. They pick up their drink and leave. Their cup gets tossed.

From Lamport’s paper:

// Entry protocol
turn[i] = 1                              // step 1: hand on the counter
turn[i] = max(turn[1..n]) + 1            // step 2: take a number

for j in 1..n where j != i:              // step 3: wait your turn
    while turn[j] != 0                   //   if j is in the queue
      AND (turn[j], j) < (turn[i], i):   //   and j's position beats mine
        skip                             //   then wait

// Critical section                      // step 4: get served
do_work()

// Exit protocol
turn[i] = 0                              // step 5: leave the queue

That’s it. Five steps. The entire algorithm fits in a dozen lines of pseudocode, and every single line maps to something you can physically see happening in a coffee shop.

Lamport Shenanigans: where this lives today

The Bakery Algorithm itself isn’t used verbatim in modern systems. Hardware atomic instructions like compare-and-swap are faster and don’t need this software dance. But Lamport’s core insight, that you can establish consistent ordering among competing actors using nothing but a monotonically increasing counter and a tiebreaker, is everywhere. Lamport clocks in distributed systems. Kafka, Cassandra, and CockroachDB all use logical clocks descended directly from this idea. When Kafka assigns an offset to a message, it’s solving the same problem: how do you order events happening in parallel across machines with no shared clock? The answer is the same one Lamport wrote down in 1974. Give everyone a number, use it to establish ordering. Postgres transaction IDs. Every transaction in Postgres gets a monotonically increasing integer. “Can this transaction see that row?” is answered by comparing transaction IDs, a ticket comparison, exactly like the bakery queue. The visibility rules in Postgres MVCC are the waiting loop in disguise.

Go’s sync.Mutex and Java’s AbstractQueuedSynchronizer. Both implement FIFO queuing for threads contending on a lock, the same fairness guarantee the Bakery Algorithm provides. The implementation uses hardware atomics instead of plain reads and writes, but the queueing logic is the same idea. Threads take a number and wait their turn. Raft and distributed consensus. The rkv store I’m currently building uses Raft for consensus. Raft’s leader election uses term numbers, monotonically increasing integers that establish which leader is current and which messages to ignore. A node with a stale term number is like someone trying to claim an order that’s already been picked up. The term number is the ticket.

The takeaway

Don’t forget two quid Starbucks drinks on Tuesday. Nah, I’m kidding, for real though.. it’s a steal.

Lamport’s insight was that coordination doesn’t require special hardware or a central authority. It requires a consistent way to establish ordering, a queue with unambiguous tiebreaking. The coffee shop figured that out long before computers existed. Lamport formalised it. And now it underpins half the distributed systems running in production today. Next time you’re standing in a queue, slightly zombified, waiting for your iced latte: you’re participating in a distributed algorithm. A pretty well-designed one, at that.