Networks and Distributed Systems PhD Seminar

2011 Oct 28 at 13:30

DC 1331

Online Event-Pattern Matching

Sukanta Pramanik, PhD candidate, David R. Cheriton School of Comp. Sci., Univ. Waterloo

For a system of distributed processes, online monitoring to find the occurrence of interesting patterns of events is a difficult problem. Even for a simple pattern, once an event matches a portion of the pattern, it must be retained as long as it is possible to combine it with future events to make a complete match. A bounded-memory monitor should therefore report a subset of all possible matches so as to limit the amount of information it needs to retain. We investigate a monitor that reports at least one match per trace for each primitive event that appears in the pattern.

An obvious candidate for storing the matched events is a tree as it can nicely represent the causality structure of the pattern. As a bounded-memory monitor should store a finite number of matches for each node in the tree, we need some way to determine such a subset. Unfortunately, this process requires looking beyond the subtree rooted at the node to ensure completeness. Currently we are investigating the possibility of storing the pattern as a finite automaton. It circumvents the completeness problem experienced in the tree-based approach by creating a state for an incomplete match as well as a partial match. We discuss how it can provide a shorter response time at the expense of more states, the number of which can be exponential in the length of the pattern in the worst case.