Causality-based predicate detection across space and time

This paper presents event stream-based online algorithms that fuse the data reported from processes to detect causality-based predicates of interest. The proposed algorithms have the following features. 1) The algorithms are based on logical time, which is useful to detect "cause and effect" relationships in an execution. 2) The algorithms detect properties that can be specified using predicates under a rich palette of time modalities. Specifically, for a conjunctive predicate φ, the algorithms can detect the exact finegrained time modalities between each pair of intervals, one interval at each process, with low space, time, and message complexities. The main idea used to design the algorithms is that any "cause and effect" interaction can be decomposed as a collection of interactions between pairs of system components. The detection algorithms, which leverage the pairwise interaction among the processes, incur a low overhead and are, hence, highly scalable. The paper then shows how the algorithms can deal with mobility in mobile ad hoc networks.