Testing concurrent software systems

Two approaches to testing concurrent software are presented. In the first, a system is assumed to contain a deterministic computation when correct, and I describe two testing algorithms to optimally achieve coverage of a testing metric involving racing pairs of messages. In the second approach, the system model is improved to allow additional nondeterministic behavior when it is either commutative in nature or localized in its effect. I present two sets of algorithms. The first detects whether or not a system is deterministic (i.e., no race conditions affect the computation’s outcome). The second algorithm identifies localized non-determinism, and can be used to determine whether or not a system converges to a deterministic end.