2
$\begingroup$

Lamport's Bakery Algorithm 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. 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.

$\endgroup$
  • 2
    $\begingroup$ Chapter 4 of Distributed Computing by Attiya and Welch treats this in detail. $\endgroup$ – Aaron Sterling Aug 10 '11 at 0:12
  • $\begingroup$ The Attiya-Welch book infact proves the algorithm for atomic registers, not safe registers, so am not sure it addresses my question $\endgroup$ – kryptos Aug 10 '11 at 11:15
  • $\begingroup$ 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. $\endgroup$ – Aaron Sterling Aug 10 '11 at 14:58
  • $\begingroup$ 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. $\endgroup$ – Aaron Sterling Aug 10 '11 at 15:00
  • 1
    $\begingroup$ 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, which assumes atomic registers. $\endgroup$ – Aaron Sterling Aug 10 '11 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.