Foundations of Event Correlation

摘要0430102斯坦福大学该项目的目标是发展事件相关性的统一理论。事件关联是发布-订阅系统中非常强大的技术，是嵌入式系统日益流行的架构设计选择。事件关联允许组件通过中间件订阅复杂的事件时间模式，而不是像事件过滤中那样订阅单个事件。这有几个优点：它通过减少网络流量和不必要的组件激活以及实现更准确的组件调度来提高性能；它通过将功能从组件转移到中间件中的标准服务来简化系统开发；最后，它通过明确组件依赖关系来提高可分析性，从而使系统更加可靠。 尽管有这些优点，事件相关性却很少被使用。 原因是系统开发人员不信任现有的实现：缺乏保证所有相关事件确实传递的理论基础。研究人员正在开发一个事件关联的理论框架，该框架解决以下基本问题： *不同事件关联语言的表达性及其操作模型之间的关系； * 用于运行时评估的数据类型和算法； * 相关算法分析问题的复杂性； * 形式化测试和验证工具的开发。这项研究是形式化方法应用的一个新方向。其出发点是研究人员为 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.