What terminology do you use to describe something that is non-deterministic due to timing, but correct?

I use 'race condition', but if you reserve that for something with bugs you'll need to invent a new term for the benign version.

> What terminology do you use to describe something that is non-deterministic due to timing, but correct?

"Non-deterministic" works? However, I'm arguing that nondeterministic results from deterministic input are themselves a mild form of bug, like a compiler warning or "code smell".

Perhaps we also have to talk about causality and serialisability, clocks and timestamping. In a concurrent or distributed system it may not be easy to determine what order things happen in without unreasonable effort or performance impairment, but if so the system has to be designed so that doesn't matter.

> Think of two worker threads pushing entires to a synchronised log. It's non-deterministic which order they arrive in the log, as different schedulings and other things will cause the threads to run in different orders (they 'race' to put entries in the log, we say), but it's not a bug, and it's not lock-free because the log is synchronised.

Those I would call independent. Unless they're acting on something in common, in which case having the transactions serialised as A before B then logged as B before A is immensely annoying.

"Non-deterministic" totally works, but it's not necessarily a bug or even a code smell even if deterministic inputs lead to non-deterministic results. The order a series of parallel network calls returns is non-deterministic, for instance, but hardly a bug.

Otherwise, yes, agreed on all counts. It's telling that even when posing the question of what other term to use besides race condition, the op used 'non-deterministic'.

Since pjc wanted a example that isn't explicitly a bug (a 'benign' race condition) I'll provide one that can be a major pita, two concurrent tasks are logging their event stream. Logs may not hit in exactly the order that you expect in your mind, forcing you to stop and think each time you're going over the logs. Definitely a race condition. Definitely expected behaviour. Not sure you can call that a bug.

More than once in my life I have thought that this was a bug, tried to correct it, and introduced another bug, followed by teeth gnashing, hair pulling, swearing, and then a revert.

> ...is generally called "lock free"

No that doesn't always apply.

Think of two worker threads pushing entires to a synchronised log. It's non-deterministic which order they arrive in the log, as different schedulings and other things will cause the threads to run in different orders (they 'race' to put entries in the log, we say), but it's not a bug, and it's not lock-free because the log is synchronised.

I think it's a little unfair to characterize GP's comment as sniping. Race conditions don't necessarily involve schedulers, or CPUs operating on memory locations. It's true that concurrent processes that work correctly without synchronization are often called lock-free, but I don't see how that refutes the original point.

Given the context, and the confusion about what race conditions even are in some of the comments in the thread, I'd say the comment opened some good discussion. GP also provided examples of race conditions that are simple to reason about elsewhere in the thread, and also explained the difference between race conditions in general, and data races.

> Code that is proven to work correctly without using synchronisation primitives, ie across the possible interleavings, is generally called "lock free"

Informally, some people use it for that. But lock-free code is not that.

You may have lock-free code with locks, or lock-free code without data races, or lock-free code that can be shown to be incorrect (by your definition) yet work for the designed purpose...

> You may have lock-free code with locks

That doesn't sound right. I suppose you could have locks in the trivial sense, where it never actually blocks, but I don't imagine that's what you meant.

https://concurrencyfreaks.blogspot.com/2013/05/lock-free-and...

https://www.cs.yale.edu/homes/aspnes/pinewiki/ObstructionFre...

Your first link confirms you can have locks in a multithreaded lock free algorithm - "The Lock-Free property guarantees that at least some thread is doing progress on its work" - I always thought this property should have been called deadlock free.

That's a good point, it does seem consistent with that definition.

This other blog post [0] seems to use a stricter definition of lock-free which precludes any way to schedule threads which would cause progress to cease indefinitely. That seems to be what the ConcurrencyFreaks blog refers to as Wait-free.

Any experts in lock-free programming able to clarify things?

[0] https://preshing.com/20120612/an-introduction-to-lock-free-p...

> You may have lock-free code with locks

I don't see how you can have that. If one process holding a lock halts then it will prevent system-wide progress, which is not allowed in the definition of 'lock-free'.

> If one process holding a lock halts then it will prevent system-wide progress

As others have mentioned already, if you had code that did that, that code would not be "lock-free". Lock-free requires progress in all circumstances even in the presence of ordering primitives (what we colloquially call "locks").

> if you had code that did that, that code would not be "lock-free"

Are you replying to the right person? That's what I just explained to the person I was replying to. You've quoted part of my comment but left out the "...which is not allowed in the definition of 'lock-free'".

Did I? Ha ha, looks like I was preaching to the choir…

> You may have lock-free code with locks

That doesn't sound very lock-free?