ITR: Self-Stabilizing Networking Protocols for Distributed Systems

容错协议对于在大型动态分布式系统中提供各种服务（路由、组通信、广播、多播等）至关重要，在这些系统中，处理器和通信链路都可能间歇性地发生故障。例如，在移动和自组织网络中，通信链路不可靠，某些节点可能在一定时间内无法到达。这种网络由移动主机组成，通过无线无线电信道进行通信，正越来越多地用于局域网、执法、军事行动和无数其他应用。传统的容错协议设计方法假定了错误数量的上界，并采用了错误屏蔽的最坏情况设计。虽然这种方法在假定的条件下提供100%的系统可用性，但实现的成本非常高。同时，有许多应用程序在很短的时间内缺乏系统可用性是可以接受的。自稳定是设计分布式容错系统的“乐观”模型；错误数量没有上限是必要的，系统总是从任意（可能是非法的）状态开始达到合法的全局状态，并且不需要中央控制。但是，在收敛期间，系统的可用性不能保证。本研究针对动态分布式系统的全局通信原语进行容错自稳定协议的设计与分析，特别适用于移动自组织网络。研究主要集中在以下几个方面：—创建自稳定分布式算法的设计范式和指导原则；——探索将传统算法转化为自稳定模拟的方法；发现和分析网络中全球通信原语（资源中心位置，领导者选举等）的自稳定协议；——探索分数（有理）值自稳定算法作为一种方法，以获得改进的近似解，否则np困难的问题；——测量自稳定算法可以包含单个故障的程度。该研究采用理论与实验相结合的方法，并将其结果应用于新兴的自组网分布式应用。

Fault tolerant protocols are essential for providing various services (routing, group communication, broadcasting, multi-casting, etc.) in large, dynamic, distributed systems, where both processors and communication links can malfunction intermittently. For example, in mobile and ad hoc networks, the communication links are unreliable and some nodes may be unreachable for certain amounts of time. Such networks, consisting of mobile hosts that communicate via wireless radio channels, are being increasingly used for local area networks, law enforcement, military operations and a myriad of other applications. The traditional approach in designing fault tolerant protocols assumes an upper bound on the number of faults and involves a worst case design by fault masking. While this approachprovides 100% system availability under assumed conditions, the implementation becomes very expensive. At the same time there are numerous applications for which the lack of system availability for very short periods is acceptable. Self-stabilization is an ``optimistic'' model to design distributed fault tolerant systems; no upper bound on the number of faults is necessary, systems always reach a legitimate global state starting from any arbitrary (possibly illegitimate) state, and no central control is needed. However, system availability is not guaranteed during the convergence period.This research addresses the design and analysis of fault tolerant self-stabilizing protocols for global communication primitives for dynamic distributed systems, especially suitable for mobile ad hoc networks. The research focuses on several aspects:-- Create paradigms and guiding principles for designing self-stabilizing distributed algorithms;-- Explore methodologies for translating a conventional algorithm into a self-stabilizing analog;-- Discover and analyze self-stabilizing protocols for global communication primitives (resource center location, leader election, etc.) in a network;-- Explore fractional (rational) valued self-stabilizing algorithms as a way to obtain improved approximate solutions to otherwise NP-hard problems;-- Measure the degree to which self-stabilizing algorithms can contain a single fault.The research takes a combined theoretical and experimental approach, and applies its results to emerging distributed applications for ad hoc networks.