Fault-Tolerance and Locality in Distributed Network Algorithms

这项工作是关于异步数值中的两个算法主题：容错和局部性。容错理论工作的实际意义往往是有限的，因为对可能的故障模式做出了特定的假设。在某些应用中，做出不合理的假设可能会产生严重的后果。本研究的主要目标是建立一个容错通信协议的基本理论，并且将该理论应用到实际的网络任务中。作为一般方法，提出了一种新的自稳定框架。自稳定是一种基本的稳健性属性，它使系统在任意故障模式之后能够返回到正确的操作。传统的网络管理协议使用局部性，要求所有站点维护有关网络拓扑的完整信息。在大型网络中，此任务变得非常复杂。在高速环境中，所需的全局状态改变速率可能比传播延迟快得多，因此不可能获得网络的全局状态的准确图像。容错性和局部性是确保整个系统在极端应力条件下正常退化的关键。提出了一种通用的网络分解方法，该方法允许对各种网络任务进行这种性质。已经有广泛的重要应用证明这种方法是成功的，包括网络路由、分布式目录、移动用户的在线跟踪、资源分配和负载平衡、网络同步、最短路径、死锁避免等。对于这些任务，我们的方法第一次产生了几乎最优的解决方案。

This proposed work is on two algorithmic topics in asynchronous numerics: fault-tolerance and locality. The practical significance of theoretical work in fault-tolerance is often limited because of particular assumptions made about possible fault patterns. In some applications, making unjustifiable assumptions could have grave consequences. The major goals of this research are to develop a basic theory of fault-tolerant communication protocols, that will be free of unnecessary assumptions, and to apply this theory to real network tasks. As a general approach a novel self-stabilization framework is proposed. Self-stabilization is a basic robustness property that enables the system to return to correct operation after an arbitrary pattern of failures. Traditional network management protocols use locality requiring all sites to maintain full information about the network topology. This task becomes very complex in large networks. In a high-speed environment, the required rate of global state change may be much faster than the propagation delay, thus making it impossible to obtain an accurate picture of the global state of the network. Fault- tolerance and locality properties are crucial to ensure graceful degradation of the overall system under conditions of extreme stress. A universal network decomposition approach is proposed, that allows such properties for a variety of network tasks. There is already a wide range of important applications for which this approach has proved to be successful, including network routing, distributed directories, online tracking of mobile users, resource allocation and load balancing, network synchronization, shortest paths, deadlock avoidance, and others. For these tasks our approach yields, for the first time, almost optimal solutions.