Foundations of Event Correlation

Stanford University, Stanford CA

Investigators

Abstract

Abstract 0430102 Stanford University The objective of this project is to develop a unified theory of event correlation. Event correlation is a very powerful technique in publish-subscribe systems, an increasingly popular architectural design choice for embedded systems. Event correlation allows components to subscribe with the middleware with complex temporal patterns of events rather than with single events as in event filtering. This has several advantages: it improves performance by reducing network traffic and unnecessary component activations and by enabling more accurate component scheduling; it simplifies system development by transferring functionality from components to a standard service in the middleware; and finally, it increases analyzability by making component dependencies explicit, and hence can make systems more reliable. Despite these advantages event correlation is hardly being used. The reason is that system developers do not trust existing implementations: theoretical foundations that guarantee that all relevant events are indeed delivered are lacking. The investigators are developing a theoretical framework for event correlation that addresses the following fundamental problems: * the expressiveness of different event correlation languages and the relations among their operational models; * the datatypes and algorithms for their run-time evaluation; * the complexity of associated algorithmic analysis problems; * the development of formal testing and verification tools. This research is a new direction in the application of formal methods. Its starting point was the development of an event-correlation language by the investigators for the Boeing Bold Stroke platform under the DARPA PCES program. The current project develops the theoretical foundations for that language, and extends it with memory and real-time facilities to accommodate more sophisticated event forwarding strategies and systems with real-time constraints. Efficient analysis algorithms, based on automata theory, are being developed to enable system verification and optimization. These languages, models, and algorithms are evaluated on actual complex embedded systems. The results of this research will benefit embedded systems development at many levels: * a formal semantics will give system developers the confidence to use complex correlation patterns, which provides a concise and easily comprehensible way to express event dependencies; * a hierarchy of operational models will allow compilers to generate efficient implementations, appropriately choosing the best space/time/parallelism tradeoffs according to the target platform; * solutions to the underlying decision problems will lead to the development of practical reasoning tools, such as compilers implementing complex optimizations of correlators, static analysis tools, and run-time monitors.