<p>Lamport's <a href="http://research.microsoft.com/en-us/um/people/lamport/pubs/bakery.pdf" rel="nofollow">Bakery Algorithm</a> is one of the most elegant algorithms for mutual exclusion. The beauty of it is that it works even when the underlying system only provides a weak form of registers called <em>safe registers</em>. Informally, when a read operation of a safe register is concurrent with a write to the register by another process,  the read may return any value in the domain of the register. I recently read that the Algorithm can be simplified if we want to ensure mutual exclusion with just atomic registers. Atomic registers being those in which a read of the register always returns the <em>latest</em> written value of the register i.e. operations on the register can be <a href="http://en.wikipedia.org/wiki/Linearizability" rel="nofollow">linearized</a>. I would expect that the algorithm can be simplified for atomic registers since given reading and writing are atomic, devising a mutual exclusion algorithm must be simpler. I cannot however seem to think of a simplification to the original algorithm for atomic registers.</p>

CC BY-SA 3.0
2011-08-10T00:12:46.123Z
Chapter 4 of Distributed Computing by Attiya and Welch treats this in detail.
Aaron Sterling
CC BY-SA 3.0
2011-08-10T11:15:02.237Z
The Attiya-Welch book infact proves the algorithm for atomic registers, not safe registers, so am not sure it addresses my question
kryptos
CC BY-SA 3.0
2011-08-10T14:58:36.620Z
The Bakery Algorithm, as such, is not implementable on real-world systems, because the numbers on the tickets increase without bound.  There are bounded-number variations of the bakery algorithm, which are much simpler if the registers are atomic than if they are weaker, eg safe.  Attiya and Welch give two such algorithms in that chapter: one in which a processor's waiting time depends on the number of processors in the system, and another where a processor's waiting time depends only on the amount of contention for the resource. Those algorithms require atomic registers, as written.
Aaron Sterling
CC BY-SA 3.0
2011-08-10T15:00:37.057Z
If you don't consider my comment to be addressing your question, it would help if you could post the original context you saw the "atomic registers allow Bakery to be simpler" quote in.  The Bakery Algorithm is maybe ten lines of pseudocode, and I don't see how that pseudocode could be much simpler.
Aaron Sterling
CC BY-SA 3.0
2011-08-10T17:51:25.717Z
Infact, it is mentioned in the Nancy Lynch book where they describe the Bakery Algorithm (Introduction of Section 10.7). True, the algorithm consists of essentially 3 steps, entering the Doorway, acquiring the max timestamp and waiting section, which is why the question intrigues me!
kryptos
CC BY-SA 3.0
2011-08-10T18:17:13.123Z
I don't see how to respond to you further if you won't edit your question to post the quote and the context it appeared in.  Perhaps you will find what you need in this paper on the [Black White Bakery Algorithm](http://www.google.com/m/url?client=ms-android-verizon&ei=ZslCTtCpIcKt8AaQ-4OmAg&gl=us&hl=en&q=http://www.cs.tau.ac.il/~afek/gadi.pdf&source=android-unknown&ved=0CBQQFjAA&usg=AFQjCNEGdRkbSbR4E3LHbL2fCEXLMjn_8g), which assumes atomic registers.
Aaron Sterling
CC BY-SA 3.0
2011-08-11T18:43:02.910Z
Does it matter?In any case, if we think the algorithm cannot be simplified for atomic registers, i am willing to accept that if someone shows me a proof. I am not sure what else can be added to the question except that a reputed book claims it can be simplified for atomic registers. Recall that the original algorithm from Lamport was designed with the goal of providing mutual exclusion without assuming mutual exclusion for individual accesses.
kryptos
CC BY-SA 3.0
2011-10-12T23:50:02.770Z
This question seems to be exercise 10.26 in Lynch's book.
Jukka Suomela
<dc.distributed-comp><concurrency>
On the Bakery Mutual exclusion Algorithm
kryptos
# On the Bakery Mutual exclusion Algorithm

(Asked by: username_0 on 2011-08-09)

Lamport's [Bakery Algorithm](http://research.microsoft.com/en-us/um/people/lamport/pubs/bakery.pdf) is one of the most elegant algorithms for mutual exclusion. The beauty of it is that it works even when the underlying system only provides a weak form of registers called *safe registers*. Informally, when a read operation of a safe register is concurrent with a write to the register by another process, the read may return any value in the domain of the register. I recently read that the Algorithm can be simplified if we want to ensure mutual exclusion with just atomic registers. Atomic registers being those in which a read of the register always returns the *latest* written value of the register i.e. operations on the register can be [linearized](http://en.wikipedia.org/wiki/Linearizability). I would expect that the algorithm can be simplified for atomic registers since given reading and writing are atomic, devising a mutual exclusion algorithm must be simpler. I cannot however seem to think of a simplification to the original algorithm for atomic registers.

**Tags:** dc.distributed-comp, concurrency
> **Comments:**
> **username_1**: Chapter 4 of Distributed Computing by Attiya and Welch treats this in detail.  
> **username_0**: The Attiya-Welch book infact proves the algorithm for atomic registers, not safe registers, so am not sure it addresses my question  
> **username_1**: The Bakery Algorithm, as such, is not implementable on real-world systems, because the numbers on the tickets increase without bound.  There are bounded-number variations of the bakery algorithm, which are much simpler if the registers are atomic than if they are weaker, eg safe.  Attiya and Welch give two such algorithms in that chapter: one in which a processor's waiting time depends on the number of processors in the system, and another where a processor's waiting time depends only on the amount of contention for the resource. Those algorithms require atomic registers, as written.  
> **username_1**: If you don't consider my comment to be addressing your question, it would help if you could post the original context you saw the "atomic registers allow Bakery to be simpler" quote in.  The Bakery Algorithm is maybe ten lines of pseudocode, and I don't see how that pseudocode could be much simpler.  
> **username_0**: Infact, it is mentioned in the Nancy Lynch book where they describe the Bakery Algorithm (Introduction of Section 10.7). True, the algorithm consists of essentially 3 steps, entering the Doorway, acquiring the max timestamp and waiting section, which is why the question intrigues me!  
> **username_1**: I don't see how to respond to you further if you won't edit your question to post the quote and the context it appeared in.  Perhaps you will find what you need in this paper on the [Black White Bakery Algorithm](http://www.google.com/m/url?client=ms-android-verizon&ei=ZslCTtCpIcKt8AaQ-4OmAg&gl=us&hl=en&q=http://www.cs.tau.ac.il/~afek/gadi.pdf&source=android-unknown&ved=0CBQQFjAA&usg=AFQjCNEGdRkbSbR4E3LHbL2fCEXLMjn_8g), which assumes atomic registers.  
> **username_0**: Does it matter?In any case, if we think the algorithm cannot be simplified for atomic registers, i am willing to accept that if someone shows me a proof. I am not sure what else can be added to the question except that a reputed book claims it can be simplified for atomic registers. Recall that the original algorithm from Lamport was designed with the goal of providing mutual exclusion without assuming mutual exclusion for individual accesses.  
> **username_2**: This question seems to be exercise 10.26 in Lynch's book.  

---

## 0 answers

