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.