I've always liked section 3 of this paper, specifically the concept that "infinite interleavings" make threads executing in parallel non-deterministic and difficult to reason about. That gets to the heart of why threaded programs are so prone to heisenbugs.
"They make programs absurdly nondeterministic, and rely on programming style to constrain that nondeterminism to achieve deterministic aims."
You can't write an infinite number of test cases for all those interleavings, and it requires hard thought to suss out where any problems might lie.
This talk was about Foundation DB was brought up recently, and it's pretty amazing. I recommend watching the whole thing, but to be brief they are taming the "infinite interleavings" problem through determinism.
"Testing Distributed Systems w/ Deterministic Simulation" by Will Wilson
They wrote an interesting Actor DSL that compiles to C++ and is completely deterministic, and they torture this deterministic engine with generated test cases on a cluster every night.
I guess you could say that the whole cluster is necessarily non-deterministic, but an individual node is deterministic, given an ordering of the messages it receives.
This is just my opinion, but I've never found that part of multi-threading difficult. Interleaving doesn't matter except where resources are shared between multiple threads, and the solution is to protect the resource with a mutex.
Sometimes it's hard to tell when a resource is shared, but that has more to do with not knowing how the code works than it does with multi-threading.
> Sometimes it's hard to tell when a resource is shared, but that has more to do with not knowing how the code works than it does with multi-threading.
With respect, this sort of thing works a lot better for small codebases where you're the only one working on it. Multithreading when you can't contain the entire relevant codebase in your brain is where the real challenge is.
My favorite one is where adding debug traces causes the heisenbug to disappear because the printf() inserted a memory fence somewhere deep in the logging library.
> To offer a third analogy, a folk definition of insanity is to do the same thing over and over again and to expect the results to be different. By this definition, we in fact require that programmers of multithreaded systems be insane. Were they sane, they could not understand their programs.
I actually had this exact notion when implementing pthreads for a course. I noted to myself "Gee, I keep doing the same thing and every time I get a different result... I must be insane according to the definition"
"They make programs absurdly nondeterministic, and rely on programming style to constrain that nondeterminism to achieve deterministic aims."
You can't write an infinite number of test cases for all those interleavings, and it requires hard thought to suss out where any problems might lie.