Fast Convex Closure for Efficient Predicate Detection

The behaviour of parallel and distributed programs can be modeled as the occurrence of events and their interrelationship. Event data collected according to the event model is stored within a partial-order data structure, where it can be reasoned about, enabling debugging, program steering, and autonomic feedback control of the application. Reasoning over event data, a critical requirement for autonomic computing, is typically in the form of predicate detection, a search mechanism able to detect and locate arbitrary predicates within the event data. To enable hierarchical predicate detection, compound events are formed by computing the convex closure of the matching primitive events. In particular, the Xie and Taylor convex-closure algorithm forms the basis for such an approach to predicate detection. Unfortunately, their algorithm can be quite slow, especially for hierarchical compound events. In this paper, we study the cause of the problems in the Xie and Taylor algorithm. We then develop an efficient extension to their algorithm, based on a simple caching scheme. We prove our algorithm correct. We also provide experimental results that demonstrate that our approach reduces the execution time of the Xie and Taylor algorithm by up to 98 percent.