Efficient global event predicate detection

Detection of global event predicates is an important issue for distributed systems, particularly for debugging and monitoring of such systems. The paper defines event normal form (ENF) event predicates, and two online algorithms to detect the first occurrence of such predicates. These algorithms differ in the technique used to match concurrent groups of events. The first builds and searches a tree of a possible matches. The second algorithm achieves the same result as the first, but needs only a single node of the tree at any time, resulting in better space and time complexity. We outline correctness proofs, and provide performance measurements from an implementation