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^3n^3\log mn). We give two algorithms, a deterministic algorithm with time complexity O(mn) and work complexity O(mn^2), and a randomized algorithm with time complexity (mn)^{1/2 + o(1)} and work complexity O(mn^2). \% and two offline algorithms. The online deterministic algorithm has. Furthermore, our algorithms improve upon the space complexity of ParallelCut . Both of our algorithms have space complexity O(mn^2) whereas ParallelCut has space complexity O(m^2n^2).
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^3n^3\log mn). We give two algorithms, a deterministic algorithm with time complexity O(mn) and work complexity O(mn^2), and a randomized algorithm with time complexity (mn)^{1/2 + o(1)} and work complexity O(mn^2). Furthermore, our algorithms improve upon the space complexity of ParallelCut . Both of our algorithms have space complexity O(mn^2) whereas ParallelCut has space complexity O(m^2n^2).
R
NC
NC
R
ParallelCut
ParallelCut
D
\% and two offline algorithms. The online deterministic algorithm has.
R
ParallelCut
ParallelCut
R
ParallelCut
ParallelCut