[noiseman]

>The proof of correctness of the algorithm revealed that the read or write of an entire number need not be atomic. The bakery algorithm is correct as long as reading a number returns the correct value if the number is not concurrently being written. It doesn't matter what value is returned by a read that overlaps a write. The algorithm is correct even if reading a number while it is changing from 9 to 10 obtains the value 2496.

How?

[k4rtik]

> It doesn't matter what value is returned by a read that overlaps a write. The algorithm is correct even if reading a number while it is changing from 9 to 10 obtains the value 2496.

There are two variables involved in the bakery algorithm[1] -- choosing[k] and number[k]:

- choosing[k] takes only the two values 0 & 1, hence reading/writing to it is atomic.

- number[k] is boundless, hence the question of inconsistency while reading it. Lamport shows (see Assertion 2's Proof in [1]) that given,

  1. tL2 < tL3 (on process i), and
  2. te < tw < tc (on process k),

(in the non-trivial case) tc can only occur before tL2 (tc < tL2) => tw < tL3, that is process i reads the current value of number[k]. See, no overlap! "The bakery algorithm is correct as long as reading a number returns the correct value if the number is not concurrently being written".

I think it is much easier to understand with the two-arrow formalism presented later in the article.

[1]: http://msr-waypoint.com/en-us/um/people/lamport/pubs/bakery....

[yshalabi]

It comes down to how you define correctness. Weaker consistency requirements accept executions that do not serialize processor orderings allowing for algorithms like bakery to work without strong atomic operations.