Jiri Simsa, Randy Bryant, Garth A. Gibson, Jason Hickey (Google)
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213
Systematic testing, first demonstrated in small, specialized cases 15 years ago, has matured sufficiently for large-scale systems developers to begin to put it into practice. With actual deployment comes new, pragmatic challenges to the usefulness of the techniques. In this report we are concerned with scaling dynamic partial order reduction, a key technique for mitigating the state space explosion problem, to very large clusters. In particular, we present a new approach for distributed dynamic partial order reduction. Unlike previous work, our approach is based on a novel exploration algorithm that 1) enables trading space complexity for parallelism, 2) achieves efficient load-balancing through time-slicing, 3) provides for fault tolerance, 4) has been demonstrated to scale to more than a thousand parallel workers, and 5) is guaranteed to avoid redundant exploration of overlapping portions of the state space.
KEYWORDS: Systematic Testing, Stateless Exploration, State Space Reduction, Parallel Processing
FULL TR: pdf