5 ms·

Slight nitpick - the definition of "race condition" on Wikipedia [0] is: [...] the condition of an electronics, software, or other system where the system'

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 https://en.wikipedia.org/wiki/Race_condition

deleted 4y ago
[deleted]
worewood 4y ago
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.
chrisseaton 4y ago
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.
- User23 4y ago
  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.
  - tonyarkles 4y ago
    > 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.
    - tialaramex 4y ago
      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.
      - kaba0 4y ago
        It can overflow, but integer math is associative and commutative still, isn’t? It’s just modulo the biggest representable number (if unsigned).
  - 4y ago
mizzao 4y ago
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.
- deleted 4y ago
  [deleted]
shwestrick 4y ago
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.
- kazinator 4y ago
  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?"
  - shwestrick 4y ago
    Whoa, uhh, I mean, that's an extremely unfair and inaccurate characterization.
    - kazinator 4y ago
      Sure, and one that one can avoid bringing on oneself by not abusing/twisting/redefining common terminology.
      - bheadmaster 4y ago
        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.
        4y ago
squeaky-clean 4y ago
> 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_research https://en.m.wikipedia.org/wiki/Wikipedia:No_original_resear...
- bheadmaster 4y ago
  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 https://www.wordnik.com/words/race%20condition [1] https://www.techtarget.com/searchstorage/definition/race-condition https://www.techtarget.com/searchstorage/definition/race-con... [2] https://techterms.com/definition/race_condition https://techterms.com/definition/race_condition [3] https://www.javatpoint.com/what-is-race-condition https://www.javatpoint.com/what-is-race-condition [4] https://www.techopedia.com/definition/10313/race-condition https://www.techopedia.com/definition/10313/race-condition

deleted 4y ago

[deleted]

worewood 4y ago

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.

chrisseaton 4y ago

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.

User23 4y ago
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.
- tonyarkles 4y ago
  > 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.
  - tialaramex 4y ago
    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.
    - kaba0 4y ago
      It can overflow, but integer math is associative and commutative still, isn’t? It’s just modulo the biggest representable number (if unsigned).
- 4y ago

mizzao 4y ago

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.

deleted 4y ago
[deleted]

shwestrick 4y ago

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.

kazinator 4y ago
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?"
- shwestrick 4y ago
  Whoa, uhh, I mean, that's an extremely unfair and inaccurate characterization.
  - kazinator 4y ago
    Sure, and one that one can avoid bringing on oneself by not abusing/twisting/redefining common terminology.
    - bheadmaster 4y ago
      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.
      - 4y ago

squeaky-clean 4y ago

> 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_research https://en.m.wikipedia.org/wiki/Wikipedia:No_original_resear...

bheadmaster 4y ago
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 https://www.wordnik.com/words/race%20condition [1] https://www.techtarget.com/searchstorage/definition/race-condition https://www.techtarget.com/searchstorage/definition/race-con... [2] https://techterms.com/definition/race_condition https://techterms.com/definition/race_condition [3] https://www.javatpoint.com/what-is-race-condition https://www.javatpoint.com/what-is-race-condition [4] https://www.techopedia.com/definition/10313/race-condition https://www.techopedia.com/definition/10313/race-condition