Precluding useless events for on-line global predicate detections

Detecting global predicates is an important task in testing and debugging distributed programs. In this paper, we propose an approach that effectively precludes useless events for global predicate detection, facilitating the process of an independent on-line checking routine. To identify more useless events than a simple causality-check method can do, our method tracks and maintains the precedence information of event intervals as a graph. To reduce the potentially expensive space and time cost as the graph expands, we propose an effective scheme to prune the graph. The performance of our method is analyzed and evaluated by simulations. The result shows that our approach outperforms conventional approaches in terms of the number of useless events found.