Choosing among alternative pasts

The primary difficulty with testing concurrent programs is their non‐determinism, where two executions with the same input can yield different results due to a changed thread schedule (also known as interleaving). This problem is aggravated by the fact that most thread schedulers are almost deterministic, and generate the same interleavings over and over for a given testing environment. The traditional approach to testing concurrent programs is to identify and examine the race conditions. A different solution involves noise‐making, which generates different interleavings at runtime, for example, using embedded sleep statements. This paper proposes a totally different technique for generating a rich set of interleavings. In this approach, operations on shared variables are tracked. Every time a shared variable is read, the value to be read is selected from the set of values that were held by this variable during the program execution. The algorithm identifies those values that the variable could hold in some interleaving consistent with the past observed events. Within this subset, the value choice can be random, biased‐random, based on coverage, etc. The problem of identifying read values that are consistent with the past observations is far from simple, since past decisions on value selection affect future ones. Our solution is computationally intensive and, therefore, impractical as is. However, insights gained from this solution lead to new heuristics for noise‐making. Copyright © 2006 John Wiley & Sons, Ltd.