Notes on nondeterminism in message passing programs

Nondeterministic program behavior can lead to different results in subsequent program runs based on the same input data. This kind of problem can be seen in any program, but is even magnified in a parallel execution context due to the existence of several independent but communicating tasks. Even though this kind of nondeterminism is commonplace and in many cases even useful for the implementation of applications, it often leads to sporadically occurring errors. These bugs are difficult to reproduce and represent a heavy challenge during testing and debugging. The biggest problem, however, may be the unawareness of users about the existence of nondeterministic choices and their consequences. In order to raise the awareness and to provoke discussions about this serious problem, this paper provides an exemplary overview of nondeterministic behavior in message passing programs. With simple examples, it is demonstrated how nondeterminism can vigorously affect the behavior and the final results of software and how the behavior can change between different architectures.