Talk:Lamport's bakery algorithm

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing articles
???	This article has not yet received a rating on the project's importance scale.

Computer science Mid‑importance

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

Mid

This article has been rated as Mid-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

It's, of course, of no theoretical import ... but might it seem a bit more natural to computer scientists to index the array from [0..N-1]? This follows more closely how many programming languages work.

I agree so that we maintain consistency. JWHPryor 15:45, 22 December 2006 (UTC)JWHPryor[reply]

I think the "critical section" and "non-critical section" should be moved out of the article as they apply to all concurrency articles. There should just be a link. JWHPryor 15:45, 22 December 2006 (UTC)JWHPryor[reply]

I disagree. It's handy to have a quick summary to refresh your memory in addition to a link to the main section for further details. 67.6.222.36 (talk) 22:52, 24 June 2011 (UTC)[reply]

The "pseudocode" isn't pseudocode at all: it's full of semicolons, brackets, and language-specifics. Pseudocode should read like English. 86.150.130.12 22:59, 3 January 2007 (UTC)[reply]

I disagree. "Pseudocode" says what it's not, not what it is. The point is that it uses common conventions that most people will understand. Brackets are quite common for arrays. Semi's help to delineate instructions. If you remove all the "shorthand" symbols to make it read more like Engish, then it gets too wordy and starts to get ambiguous. 67.6.222.36 (talk) 22:52, 24 June 2011 (UTC)[reply]

The following is incorrect: "It is possible that more than one thread will get the same number when they request it; this cannot be avoided." With an atomic increment instruction each thread is guaranteed a unique ticket.--C0d1f1ed (talk) 06:15, 21 April 2008 (UTC)[reply]

They mean when no such primitives are available. If you have various "atomic" operations, this whole thing is unnecessary. I agree though that variations of this idea can be present in "lock free code" that avoids expensive instructions but still uses them when necessary. Długosz (talk) 18:51, 23 September 2009 (UTC)[reply]

True. This is an algorithm for when atomic operations are no available. 67.6.222.36 (talk) 22:52, 24 June 2011 (UTC)[reply]

I would like to suggest that using the syntax (a, b) < (c, d) is unnecessary and confusing; it is not, as far as I know, standard syntax in any language, and it is used in only one place within the pseudocode where the expanded form (a < c) || ((a == c) && (b < d)) is nearly as compact. Why not just use the standard syntax which is more understandable and will not expand the size of the pseudocode significantly? Eliminating this nonstandard syntax will also shorten the Wikipedia article as it will not be necessary to have the explanatory section for this syntax. — Preceding unsigned comment added by 204.176.49.46 (talk) 17:54, 16 January 2012 (UTC)[reply]

I'd like to add that I have just read Lamport's original paper and the (a, b) < (c, d) syntax is lifted directly from that paper. I can see why there was some interest in using that syntax here since it reflects Lamport's original language; but I think my point still holds: it is unnecessary, and this article would be better if it were eliminated. — Preceding unsigned comment added by 204.176.49.46 (talk) 18:18, 16 January 2012 (UTC)[reply]

I agree that it is unnecessary complexity. However I'd like to point out that the lexicographic order relation on tuples is very common in CS, and that Python is an example of a language which supports it. --203.173.240.168 (talk) 02:09, 24 January 2014 (UTC)[reply]

The Java code given here uses AtomicIntArrays, which appears to completely miss the point, since the algorithm doesn't require that any of the operations are atomic. However I don't know Java so I don't know how for sure how to fix it ("IntArray" maybe?) --203.173.240.168 (talk) 02:09, 24 January 2014 (UTC)[reply]

It should be better now — Preceding unsigned comment added by 147.83.76.247 (talk) 16:29, 11 December 2015 (UTC)[reply]

I am concerned that the algorithm as shown is not correct because it doesn't handle the overflow case. If the lock is constantly contested, I think the "Number" variable will increase without bound and eventually overflow. Also, I think this can be fixed by making two changes. First when adding 1 to the max, check that the result is not zero (overflow), and if it is then set to 1. Second use sequence number comparisons rather than unsigned magnitude comparison. I.e. (X<Y) becomes ( (signed)(X-Y) < 0 ). A zero value of Number must be handled as a special case. This is a bit tricky, and I am not sure this is correct, so perhaps others can comment. — Preceding unsigned comment added by 216.31.219.19 (talk) 15:15, 4 May 2016 (UTC)[reply]

So long as the number of threads never gets close to maximum number for integer, it won't overflow because unlocking threads will drop the max number down. Fnordware (talk) 16:25, 6 September 2023 (UTC)[reply]

Sequential consistency not required

The bakery algorithm does not require sequential consistency, but only safe registers (which can return arbitrary values when read are concurrent with writes, and are therefore clearly not sequentially consistent). Yet the article claims that the bakery algorithm does require sequential consistency. I have seen this erroneous statement cited in several places. Can I just delete the sentence? --N4n0g1g4 (talk) 16:31, 21 January 2024 (UTC)[reply]