Hacker News Reader

Comment by bheadmaster | Hacker News Reader

Slight nitpick - the definition of "race condition" on Wikipedia [0] is:

    [...] the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events

If we take the first example - Parallel BFS - the correctness of the output could be considered "system's substantive behavior". Properly implemented atomic checks (as demonstrated) would still guarantee to lead to correct output in all possible combinations of events. Therefore, the system's "substantive behavior" is not dependent on the sequence or timing of other uncontrollable events. Therefore, there is no "race condition" involved.

Of course, the term "race condition" here is taken colloquially, for the sake of familiarity to the reader - the article has correctly recognized that the appropriate term for this kind of behavior is "non-determinism".

[0] https://en.wikipedia.org/wiki/Race_condition

View on HN

I don't know where Wikipedia got this 'substantive behaviour' requirement from, but for example it explicitly isn't part of the definition in the industry's definitive reference for parallelism - Padua.

> A race condition occurs in a parallel program execution when two or more threads access a common resource, e.g., a variable in shared memory, and the order of the accesses depends on the timing, i.e., the progress of individual threads.

> The disposition for a race condition is in the parallel program. In different executions of the same program on the same input access events that constitute a race can occur in different order, which may but does not generally result in different program behaviors (non-determinacy).

Sometimes you deliberately program a full-on data race (which isn't a bug by definition, as the article says) for performance reasons.

> Data races that are not manifestations of program bugs are called benign data races.

It’s worth noting that algorithms can be designed correct under nondeterministic execution. For example, quicksort is correct with a randomly selected pivot. And for associative and commutative functions it doesn’t matter what order they’re executed in the final result is always the same.

Dijkstra’s guarded commands don’t specify an order for the conditional. The semantics is that the process is free to execute any one of the cases that has a true guard. Nevertheless he found them useful for developing and describing many algorithms.

> And for associative and commutative functions it doesn’t matter what order they’re executed in the final result is always the same.

Not directed at you specifically, but just a reminder for anyone who hasn’t been burned by it yet: floating point addition is not associative. (a+b)+c != a+(b+c). It’s close, but if you’re not careful you can get bad results where the accumulated small errors turn into wrong answers.

Not just floating point maths either. The built-in "integers" in your computer don't behave like the integers taught in school either but that's how we tend to think about them. This is why I argue trapping is the most acceptable choice for arithmetic problems in general purpose languages, if the program tries to add 150 to 150 in an unsigned 8-bit integer, that's a programming error. By all means offer wrapping arithmetic, sometimes it's what the programmer actually wanted and they benefit from being able to clarify that - but most often they didn't want that and would be astonished that 150 + 150 = 44.

It can overflow, but integer math is associative and commutative still, isn’t? It’s just modulo the biggest representable number (if unsigned).

> It’s worth noting that algorithms can be designed correct under nondeterministic execution.

In fact the whole concept of "symmetric multiprocessing" demands it.

That definition seems to conflate "determinism" (something largely impossible to achieve in asynchronously parallel systems) with "correctness" (an abstracted property of a system that doesn't have anything to do with determinism per se). It just doesn't seem useful.

No, in overwhelmingly common usage, programmers use the term "race condition" as a category of software bug. We mean it in the correctness sense, not the one used in the linked article nor your reference. You'd be met with some very weird stares if you tried to explain how arbitrary SMP ordering of log entries or whatever was a "race condition".

> That definition seems to conflate "determinism" (something largely impossible to achieve in asynchronously parallel systems)

There are plenty of examples of entirely deterministic parallel models. Fork-join for one.

I think you missed the point. Let me expand.

I mean, yes, what you say is true, but it just amounts to saying "synchronization is a solvable problem". At their core, ALL synchronization paradigms (spin polling, interrupt masking, OS-managed process suspend, hardware memory barriers, weird lockless tricks like Dekker's algorithm, you name it) can be understood to be ways of enforcing "para-determinism" on environments that don't provide it.

In SMP, things don't happen in reliable orders. They don't. They never will. They can't. But your hardware and OS platforms are smart and provide trickery so that at least you can guarantee that "some" things happen in reliable orders. And then you construct software such that correct behavior is dependent only on that subset of ordering and not everything.

Because there is no determinism in SMP, only that which you construct.

If you can't observe the non-determinism, then is it really non-determinism?

Your processor executes a single thread of instructions also in a non-deterministic order, based on complex internal state. We'd never say it was non-deterministic, as you can't detect it.

It's visible from the perspective of the software engineer who molds non-deterministic abstractions into predictable interactions for the user.

You can absolutely observe non-determinism. That's what a race condition bug is, after all. You can also observe benign nondeterminism every day in anything that records ordering. Go do a parallel make, then do it again and observe the ordering of the mtime values in the intermediate artifacts. It won't be the same.

And FWIW: CPU-internal instruction reordering is observable too, though the details there get complicated. x86 hides (almost!) all the complexity from you, but ARM's OOO is leakier and requires careful attention to memory barriers.

> No, in overwhelmingly common usage, programmers use the term "race condition" as a category of software bug

This was exactly my point.

    race condition = incorrect behavior
    non-determinism = correct behavior

Language is tricky sometimes.

By this definition, every access to a shared resource is a race condition, e.g. even when properly acquiring a lock. It is common knowledge that you introduce locks to remove race conditions so I would say something is definitely missing from the definition.

Usually you’re adding locks not to remove the race condition but to make them not a bug.

That is a valid definition but it's not the one used by everyone I know and work with. A race condition is a fault, just like a SQL injection; it could easily have referred to a programming technique but it doesn't.

I think "remove" the race condition is the wrong word. It should be "resolve" the race conditions.

The race exists because there are multiple accesses. This is resolved when there is a protocol for deciding who proceeds and who waits for the other.

Hey, I've just downloaded PADUA (http://dx.doi.org/10.1145/2633685), and skimming through it, I can't find a single mention of the phrase "race condition".

Is this the paper you're referring to? If not, could you please provide a reference to which PADUA you're referring to? I'd really like to read more on the subject, especially if the source is, as you claim, an industry reference.

David Padua, https://link.springer.com/referencework/10.1007/978-0-387-09....

Thanks!

If you have any relevant information, would you care to elaborate more on why is it considered industry standard and how did it gain such status?

This is the first time I'm hearing of both the author and the book (which probably says more about me), and it seems kind of odd that the definition differs from what is usually taught in class (at least mine). Of course, it wouldn't be the first time that popular use of some word differs from its original intended meaning, but I'm just interested in the wider historical context.

Thanks again.

I don't know what else to do but appeal to authority - it's the definition of a word after all?

https://cs.illinois.edu/about/people/faculty/padua

> David Padua has served as program committee member, program chair, or general chair to more than 70 conferences and workshops. He was the Editor-in-Chief of Springer‐Verlag’s Encyclopedia of Parallel Computing and is currently a member of the editorial board of the Communications of the ACM, the Journal of Parallel and Distributed Computing, and the International Journal of Parallel Programming.

Author here. I think it would be very strange to say that this code does not have a race condition. The whole point of the term is to identify circumstances where non-deterministic timing of events influences how you reason about correctness, which is exactly what we're doing here.

If we put on a cynical hat, your page reads like "I've never heard of lock-free algorithms based on atomic operations. I therefore must have just invented it and I get to name it: how about beneficial use of race conditions?"

Whoa, uhh, I mean, that's an extremely unfair and inaccurate characterization.

Sure, and one that one can avoid bringing on oneself by not abusing/twisting/redefining common terminology.

Eh, I personally wouldn't be so hard on someone because of language. Words don't have definite meanings on their own, it's our general agreement that makes them meaningful. And the meaning of words are often overlapping, shades-of-grey kind of deal, with even more subtle differences in individual understanding of them. Language is hard.

Moreover, polite explanations may bring enlightenment, but aggressive scoldings are almost guaranteed stop people from accepting your words, even if they're true, because in order to accept their truth, they have to accept the unpleasant implications of your words.

I think learning should generally be as pleasant as possible. Putting the work in is hard enough as it is.

> I think learning should generally be as pleasant as possible.

If you want pleasant learning on the Internet, don't "learn by teaching" through blogs that mislead other learners, even if only in terminology use.

People will tear that apart.

According to the Encyclopedia of Parallel Computing (mentioned in one of the sibling sub-comments of my original comment), you and I are both wrong in what we consider a "race condition". Of course, whether or not the source is an authority on the subject when the popular usage of the word refers to a different concept is questionable, but there's at least a possibility that we're both wrong.

Regardless, that's still one more reason not to be unpleasant to people when correcting them - you might just find yourself in the wrong.

I've personally only heard the term "race condition" used to refer to bugs that have their source in non-deterministic execution of programs. In most cases, they refer to a specific sequence of events that the programmer did not foresaw, which lead to incorrect computation.

Using the term "race condition" in context of correct programs would make it cover exactly the same universe of programs as the term "non-determinism". I that think the distinction, however trivial (race condition = incorrect behavior, non-determinism = correct behavior), is still useful.

Great article, by the way. I did not mean to criticize it in any way. My "slight nitpick" about meaning of the words is really just that - a nitpick :)

Ah I see. That's a fair point!

When talking about this kind of stuff to people who are unfamiliar with, say, lock-freedom, I've found that "non-determinism" is too vague --- people start thinking about things like randomness, or user interaction, etc. In contrast, the term "race condition" seems to hit the nail on the head.

But certainly, "race condition" also carries with it a bit of baggage ;)

I work in the Erlang VM, and we always say stuff like "whether your output to IO hits first ot the logger line outputs to IO first is a race condition". Neither is substantively wrong, and you could definitely say "it's a race!", grab some popcorn, and watch the electrons do their thing.

Why not use the right term, then? "Coloquial" shouldn't be a thing with technical terms.

Race conditions are hard enough to explain to people and misusing the term just makes it more difficult.

Interesting, it's almost like one could call this a "randomized algorithm" (which we know can be faster than deterministic algorithms) but the non-determinism comes from the input data and code execution rather than a RNG.

> This article needs additional citations for verification. (July 2010).

The definition you quote has no linked citation on Wikipedia. Usually a good sign that you should not treat those statements as definitive. A good Wikipedia article should not state any "facts" without a direct means of verification. Otherwise it's considered "original research" and against the wiki policy for a high quality article.

https://en.m.wikipedia.org/wiki/Wikipedia:No_original_resear...

I used Wikipedia in order to have some kind of reference, but I was fairly sure of the meaning beforehand.

Searching the internet for "race condition definition" and taking the top few results brings several definitions that all agree in spirit with the Wikipedia one (see below).

If you know of any more reliable source that doesn't agree with Wikipedia on the definition of "race condition", please post it here. This is a honest request - I am always grateful to those who correct my mistakes (in good faith).

    wordnik [0]:  A flaw in a system or process whereby the output or result is unexpectedly and critically dependent on the sequence or timing of other events.

    techtarget [1]: A race condition is an undesirable situation that occurs when a device or system attempts to perform two or more operations at the same time, but because of the nature of the device or system, the operations must be done in the proper sequence to be done correctly.

    techterms [2]: A race condition occurs when a software program depends on the timing of one or more processes to function correctly.

    javatpoint [3]: When the output of the system or program depends on the sequence or timing of other uncontrolled events, this condition is called Race Condition.

    technopedia [4]: A race condition is a behavior which occurs in software applications or electronic systems, such as logic systems, where the output is dependent on the timing or sequence of other uncontrollable events.

[0] https://www.wordnik.com/words/race%20condition

[1] https://www.techtarget.com/searchstorage/definition/race-con...

[2] https://techterms.com/definition/race_condition

[3] https://www.javatpoint.com/what-is-race-condition

[4] https://www.techopedia.com/definition/10313/race-condition

> If you know of any more reliable source that doesn't agree with Wikipedia on the definition of "race condition", please post it here.

Other commenters have already covered that. The links you shared aren't good primary sources, and probably took their definition from Wikipedia itself, creating a circular reference issue.

Regardless, if you yourself happen to know any sources that weren't covered in other comments, please share them.

I remember learning about race conditions in college, and they were always mentioned in the context of bugs - that's why I took Wikipedia itself for granted, as its definition fit my current understanding of the word.

It seems to be a case of popular usage of the word differing from the original. It also raises a question of whether or not the original intended meaning is the authority, if the majority of programmers use it in a different way. Who should, in general, be the authority on the meaning of a word? But that's more of a philosophical question, I suppose.

Reply on news.ycombinator.com