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%的系统可用性，但实现成本非常高。 与此同时，有许多应用程序在很短的时间内缺乏系统可用性是可以接受的。 自稳定是一种设计分布式容错系统的“乐观”模型;不需要故障数量的上限，系统总是从任何任意（可能是非法的）状态开始达到合法的全局状态，并且不需要中央控制。 然而，系统的可用性是不能保证在收敛期间，本研究地址的设计和分析的容错自稳定协议的全球通信原语的动态分布式系统，特别是适用于移动的ad hoc网络。研究集中在几个方面：--创建设计自稳定分布式算法的范例和指导原则;--探索将传统算法转换为自稳定模拟的方法;--发现和分析全局通信原语（资源中心定位，领导者选举等）的自稳定协议。在网络中;--探索分数（合理）值的自稳定算法作为一种方法，以获得改进的近似解，否则NP-难问题;--测量的程度，自稳定算法可以包含一个单一的fault.The研究采取了理论和实验相结合的方法，并将其结果应用到新兴的分布式应用ad hoc网络。