Self-Stabilizing Group Communication for Mobile Environments

点击翻译按钮获取中文摘要

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.