Repeated detection of conjunctive predicates in distributed executions
Given a conjunctive predicate phi over a distributed execution, this paper gives an algorithm to detect all interval sets, each interval set containing one interval per process, in which the local values satisfy the Definitely(phi) modality. The time complexity of the algorithm is O(n(3)p), where n is the number of processes and p is the bound on the number of times a local predicate becomes true at any process. The paper also proves that unlike the Possibly(phi) modality which admits O(p(n)) solution interval sets, the Definitely(phi) modality admits O(np) solution interval sets. The paper also gives an on-line test to determine whether all solution interval sets can be detected in polynomial time under arbitrary fine-grained causality-based modality specifications. (C) 2011 Elsevier B.V. All rights reserved.
intervals distributed computing predicate detection monitoring causality global state