Techniques to tackle state explosion in global predicate detection

Global predicate detection, which is an important problem in testing and de bugging distributed programs, is very hard due to the combinatorial explosi on of the global state space. This paper presents several techniques to tac kle the state explosion problem in detecting whether an arbitrary predicate Phi is true at some consistent global state of a distributed system. We pr esent space efficient on-line algorithms for detecting Phi. We then improve the performance of our algorithms, both in space and time, by increasing t he granularity of the execution step from an event to a sequence of events in each process.