Parallel Reachability Testing Based on Hadoop MapReduce.

Reachability testing is an important approach to testing concurrent programs. It generates and executes all the possible sequences of a concurrent program automatically with a given input while not saving any sequences that have already been executed. However, for a large and complex concurrent program, the number of synchronization sequences that are exercised is too large. It will take too long time to perform reachability testing, which limits its application. In this paper, we propose a parallel reachability testing approach based on Hadoop MapReduce called PRT, aiming to improve its performance. PRT adopts the framework of Hadoop MapReduce with a heuristic strategy to realize dynamic loading balance. We present the algorithms used in PRT, and reports the results of five concurrent Java programs that were conducted to evaluate the speed-up with respect to the sequential execution of reachability testing. Experimental results demonstrate that our PRT is an effective approach to parallelizing reachability testing.