Self-Stabilizing Group Communication for Mobile Environments

移动环境的自稳定群体通信

• 批准号: 0098305
• 负责人: Jennifer Welch
• 金额: $ 28万
• 依托单位: Texas A&M Engineering Experiment Station
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-08-01 至 2005-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0098305&HistoricalAwards=false
• 关键词: Self; Stabilizing; Group; Communication; Mobile

Group communication services form important building blocks for applications in dynamicdistributed systems, where processors and communication links can repeatedly fail and recover.Such dynamic behavior is especially descriptive of mobile environments, in which processors canchange their physical location continually. The key features of a group communication facility are(1) indicating to each processor with which other processors it can currently communicate, and (2)letting processors within a group communicate with each other in an ordered and reliable manner.A typical approach to developing fault-tolerant software is to assume certain limitations on thebehavior of faulty components. However, in reality there is a non-zero probability that any suchassumptions will be temporarily violated; in fact, this probability grows with time. In particular,mobile communication networks are exposed to environmental noise whose level is hard to predictin advance. Thus, it may be too optimistic to approach correctness by assuming that the systemis consistent initially and each subsequent step maintains consistency. Self-stabilizing algorithmscope with temporary faults in an elegant way. A self-stabilizing algorithm can be started in anyglobal state, which could be reached due to an arbitrary combination of failures, and always en-suresthat the task of the algorithm is achieved, assuming that the designer's assumptions hold forsufficiently long intervals.The goal of this research is to design self-stabilizing group communication services and applythese services to mobile networks.One part of the research will focus on the specification and design of initialized group services,in which the establishment of a new group ensures that messages related to previous incarnationsare discarded. Various synchrony assumptions will be considered in order to identify the necessaryand sufficient conditions for the specified initialized group services. One approach to be investi-gatedis using transient fault detectors that will trigger the establishment of a new group wheneverinconsistency is detected. Impossibility results will be developed to indicate which system assump-tionsare necessary; lower bound results will be proved to shed light on the degree of optimality ofthe solutions obtained. A second part of the research will study how different mobile applicationscan take advantage of the self-stabilizing group communication services developed. A third partof the research will explore the interactions between the group communication services and other,lower level, mobile services.Group communication services have been incorporated in several existing academic and indus-trialdistributed systems. However, none of them is self-stabilizing and none of them is specifi-callytailored for mobile environments. Self-stabilization and group communication are importantparadigms for the design of dynamic communication networks, and in particular wireless net-works.There is no doubt that the new methods developed in this project will contribute to futureimplementations of robust group communication systems.

组通信服务构成了动态分布式系统中应用程序的重要构建块，在动态分布式系统中，处理器和通信链路可能会反复出现故障和恢复。这种动态行为特别适合描述移动环境，其中处理器可以不断改变其物理位置。组通信设施的关键特征是（1）向每个处理器指示它当前可以与哪些其他处理器通信，以及（2）让组内的处理器以有序且可靠的方式相互通信。开发的典型方法容错软件是对故障组件的行为假设一定的限制。然而，实际上，任何此类假设暂时被违反的概率都不为零；事实上，这种可能性随着时间的推移而增加。特别是，移动通信网络暴露在难以提前预测其水平的环境噪声中。因此，通过假设系统最初是一致的并且每个后续步骤都保持一致性来接近正确性可能过于乐观。以优雅的方式实现具有临时故障的自稳定算法范围。自稳定算法可以在任何全局状态下启动，该状态可能由于任意故障组合而达到，并且始终确保实现算法的任务，假设设计者的假设在足够长的时间间隔内成立。本研究的目的是设计自稳定的组通信服务并将这些服务应用于移动网络。研究的一部分将集中于初始化组服务的规范和设计，其中新组的建立确保与以前的化身被丢弃。将考虑各种同步假设，以便识别指定的初始化组服务的必要和充分条件。一种待研究的方法是使用瞬态故障检测器，只要检测到不一致，就会触发新组的建立。将开发不可能性结果来表明哪些系统假设是必要的；下界结果将被证明可以揭示所获得的解决方案的最优程度。研究的第二部分将研究不同的移动应用程序如何利用所开发的自稳定群组通信服务。研究的第三部分将探讨群组通信服务与其他较低级别的移动服务之间的交互。群组通信服务已被纳入多个现有的学术和工业分布式系统中。然而，它们都不是自稳定的，也不是专门针对移动环境定制的。自稳定和群体通信是动态通信网络，特别是无线网络设计的重要范式。毫无疑问，该项目中开发的新方法将有助于未来实现鲁棒的群体通信系统。