Fast and Work-Optimal Parallel Algorithms for Predicate Detection

Abstract

Recently, the predicate detection problem was shown to be in the parallel complexity class NC. In this paper, we give the first work-optimal parallel algorithm to solve the predicate detection problem on a distributed computation with $n$ processes and at most $m$ states per process. The previous best known parallel predicate detection algorithm, ParallelCut, has time complexity $O(\log mn)$ and work complexity $O(m^3{n}^3\log mn)$. We give two algorithms, a deterministic algorithm with time complexity $O(mn)$ and work complexity $O(m{n}^2)$, and a randomized algorithm with time complexity $(mn{)}^{1/2+o(1)}$ and work complexity $\tilde{O}(m{n}^2)$. Furthermore, our algorithms improve upon the space complexity of ParallelCut. Both of our algorithms have space complexity $O(m{n}^2)$ whereas ParallelCut has space complexity $O(m^2{n}^2)$.

Fixed minor bug in JLSDetect from Version 3 with new subroutine FLIS