Foundations of Event Correlation

斯坦福大学这个项目的目标是发展一个统一的事件关联理论。事件关联是发布-订阅系统中的一项非常强大的技术，它是嵌入式系统日益流行的体系结构设计选择。事件关联允许组件使用复杂的事件时间模式向中间件订阅，而不是像在事件过滤中那样使用单个事件。这有几个优点：它通过减少网络流量和不必要的组件激活并通过支持更准确的组件调度来提高性能；它通过将功能从组件转移到中间件中的标准服务来简化系统开发；最后，它通过显式地使组件依赖增加可分析性，从而使系统更可靠。尽管有这些优势，事件相关性几乎没有被使用。原因是系统开发人员不信任现有的实现：保证所有相关事件确实被交付的理论基础不足。调查人员正在开发事件关联的理论框架，以解决以下基本问题：*不同事件关联语言的表达能力及其操作模型之间的关系；*其运行时评估的数据类型和算法；*关联算法分析问题的复杂性；*形式化测试和验证工具的开发。它的起点是由调查人员在DARPA PCES计划下为波音Bold Stroke平台开发事件关联语言。目前的项目开发了该语言的理论基础，并使用内存和实时设施对其进行了扩展，以适应更复杂的事件转发策略和具有实时约束的系统。基于自动机理论的高效分析算法正在被开发，以实现系统验证和优化。这些语言、模型和算法在实际的复杂嵌入式系统上进行了评估。本研究的结果将在多个层面上有利于嵌入式系统的开发：*形式化的语义将使系统开发人员有信心使用复杂的关联模式，这提供了一种简洁且易于理解的方式来表示事件依赖；*操作模型的层次将允许编译器生成高效的实现，根据目标平台适当地选择最佳的空间/时间/并行折衷；*基本决策问题的解决方案将导致开发实用的推理工具，例如实现关联器、静态分析工具和运行时监控器的复杂优化的编译器。

Abstract0430102Stanford UniversityThe 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 byenabling 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 eventcorrelation 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 itwith 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.