ITR: Self-Stabilizing Networking Protocols for Distributed Systems

ITR：分布式系统的自稳定网络协议

• 批准号: 0218495
• 负责人: Pradip Srimani
• 金额: --
• 依托单位: Clemson University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2002
• 资助国家: 美国
• 起止时间: 2002-09-15 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0218495&HistoricalAwards=false
• 关键词: ITR; Self; Stabilizing; Networking; Protocols

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.

容错协议对于在大型，动态，分布式系统中提供各种服务（路由，组通信，广播，多铸件等）至关重要，处理器和通信链接都可以间歇性地发生故障。 例如，在移动和临时网络中，通信链接是不可靠的，并且某些节点可能在一定时间内无法到达。这些网络由通过无线无线电渠道通信的移动主机组成，越来越多地用于局域网，执法部门，军事运营以及无数其他应用。设计容错协议的传统方法假定故障数量上的上限，并涉及通过故障掩盖的最坏情况设计。 尽管该方法在假定条件下提供了100％的系统可用性，但实施变得非常昂贵。 同时，有许多应用程序可以接受很短的系统可用性。 自稳定是设计分布式容错系统的``乐观''模型；从任何任意（可能是非法的）状态开始，系统始终不需要故障数量，系统始终达到合法的全球状态，并且不需要中央控制。 但是，在收敛期间不能保证系统的可用性。本研究解决了针对动态分布式系统的全球通信基原始人的耐受性自动稳定协议的设计和分析，特别适用于移动临时网络。 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作为获得改进的NP硬性问题的改进的近似解决方案的一种方式； - 测量自稳定算法的程度可能包含单个故障。研究采用了一种合并的理论和实验方法，并将其结果应用于新兴的分布式应用程序的应用网络。