> 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.
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,
(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....