« Nobody is really smart enough to program computers | Main | The real reason Google's clicks are flat »

Lamport's Bakery Algorithm

This paper describes the bakery algorithm for implementing mutual exclusion. I have invented many concurrent algorithms. I feel that I did not invent the bakery algorithm, I discovered it. Like all shared-memory synchronization algorithms, the bakery algorithm requires that one process be able to read a word of memory while another process is writing it. (Each memory location is written by only one process, so concurrent writing never occurs.) Unlike any previous algorithm, and almost all subsequent algorithms, the bakery algorithm works regardless of what value is obtained by a read that overlaps a write. If the write changes the value from 0 to 1, a concurrent read could obtain the value 7456 (assuming that 7456 is a value that could be in the memory location). The algorithm still works. I didn't try to devise an algorithm with this property. I discovered that the bakery algorithm had this property after writing a proof of its correctness and noticing that the proof did not depend on what value is returned by a read that overlaps a write.

I don't know how many people realize how remarkable this algorithm is. Perhaps the person who realized it better than anyone is Anatol Holt, a former colleague at Massachusetts Computer Associates. When I showed him the algorithm and its proof and pointed out its amazing property, he was shocked. He refused to believe it could be true. He could find nothing wrong with my proof, but he was certain there must be a flaw. He left that night determined to find it. I don't know when he finally reconciled himself to the algorithm's correctness.

...

What is significant about the bakery algorithm is that it implements mutual exclusion without relying on any lower-level mutual exclusion. Assuming that reads and writes of a memory location are atomic actions, as previous mutual exclusion algorithms had done, is tantamount to assuming mutually exclusive access to the location. So a mutual exclusion algorithm that assumes atomics reads and writes is assuming lower-level mutual exclusion. Such an algorithm cannot really be said to solve the mutual exclusion problem. Before the bakery algorithm, people believed that the mutual exclusion problem was unsolvable--that you could implement mutual exclusion only by using lower-level mutual exclusion. Brinch Hansen said exactly this in a 1972 paper. Many people apparently still believe it.

...

For a couple of years after my discovery of the bakery algorithm, everything I learned about concurrency came from studying it. ... The bakery algorithm marked the beginning of my study of distributed algorithms.
    -- Leslie Lamport

I find this story fascinating. Lamport has invented a bunch of cool algorithms. But here he describes having "discovered" the Bakery algorithm, and then spent years studying the algorithm that he had written afterwards.

How many of us find a solution to a problem, and then spend years studying the solution, learning from it? Actually I think I've learned more from studying bugs in my code than algorithms. If I could just avoid ever coding any bugs...

Lamport has done a bunch of other stuff, including inventing Paxos, the distributed consensus algorithm behind google's distributed lock manager Chubby.

Comments (4)

hey....

I'm sure I have a lot more bugs in my code.... you're more than welcome to fix them if you run out of your own bugs ;)

Kevin

AM:

Great post.

Can you elaborate (may be in a follow up posting) on the performance of mutual exclusion based on Bakery algorithm vis-a-vis say, posix mutexes ?

Anonymous:

Bakery isn't about exclusion. It's about fairness of exclusion. The same issue hits me when I think about handling event processing for a multiplayer game. How do you fairly process the action of person A before person B? What if person B's action is faster/shorter execution and would beat A to the locks even though A's command was received first by the server?

taoxu:

not me, but I know that people have been studying Adaboosting for almost 10 years now, and still going on...

Post a comment

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)

About

This page contains a single entry from the blog posted on February 22, 2008 11:06 AM.

The previous post in this blog was Nobody is really smart enough to program computers.

The next post in this blog is The real reason Google's clicks are flat.

Many more can be found on the main index page or by looking through the archives.

Powered by
Movable Type 3.33