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 /spl phi/, 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.

An optimal causal message ordering algorithm for asynchronous distributed systems was proposed by Kshemkalyani and Singhal and its optimality was proven theoretically. For a system of n processes, although the space complexity of this algorithm was shown to be O(n/sup 2/) integers, it was expected that the actual space overhead would be much less than n/sup 2/. It is difficult to determine the behavior of this algorithm by a theoretical analysis. We measure the overheads of two different implementations of the optimal causal message ordering algorithm via simulation under a wide range of system conditions. The optimal algorithm is seen to display significantly less message space overhead and log space overhead than the canonical Raynal-Schiper-Toueg algorithm.