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.