Foundations of Event Correlation

事件相关性的基础

• 批准号: 0430102
• 负责人: Zohar Manna
• 金额: --
• 依托单位: Stanford University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0430102&HistoricalAwards=false
• 关键词: Foundations; Event; Correlation

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.

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