Detecting whether a finite execution trace (or a computation) of a distributed program satisfies a given predicate, called predicate detection, is a fundamental problem in distributed systems. To solve this problem, we generalize an effective abstraction technique called computation slicing. We present polynomial-time algorithms to compute slices with respect to temporal logic predicates from a regular subset of CTL, that contains temporal operators EF, EG, and AG. Furthermore, we show that these slices contain precisely those global states of the original computation that satisfy the predicate. Using temporal predicate slices, we give an efficient (polynomial in the number of processes) predicate detection algorithm for a subset of CTL that we call regular CTL. Regular CTL contains nested temporal predicates for which, to the best of our knowledge, there did not previously exist efficient predicate detection algorithms. Then we show that we can enlarge the subset of CTL and still obtain effective results. Our algorithm has been implemented as part of a tool for analysis of distributed programs. We illustrate the effectiveness of our techniques on several protocols achieving speedups of over three orders of magnitude in one example, compared to partial order state-space search of SPIN. Furthermore, we were able to complete the verification for 250 processes for a partial order trace.
['Alper Sen', 'Vijay K. Garg']
Detecting temporal logic predicates in distributed programs using computation slicing