Design and Analysis of Distributed Algorithms for Fault- Tolerant Multiprocessor Applications

随着大规模分布式系统在安全关键应用中的应用，这些系统的容错性成为一个关键问题。本文主要研究了故障诊断和容错路由的基本问题。这项工作将首次考虑这些重要任务的协调，利用诊断信息来提高路由效率和系统吞吐量。这项工作将针对具有相对稀疏互连结构的系统，如网格、网格和超立方体，它们构成了现有系统的很大一部分，预计将主导未来的应用。提出的研究将涉及诊断和路由算法的集成设计，以及算法性能的评估，这是理论和实验性质。理论工作将利用概率分析技术，以便在最近提出的概率模型下评估性能，并检查这些系统的性能限制。实验工作将涉及在32节点英特尔IPSC/2超立方体上实现和测试所提出的算法。本研究的成果应该是针对分布式容错这些基本问题的有效算法，并可广泛应用于多处理器/多计算机系统。

As large-scale, distributed systems are used in safety-critical applications, the fault tolerance of these systems becomes a crucial issue. This research focuses on the fundamental problems of diagnosis and fault-tolerant routing. This work will, for the first time, consider the coordination of these important tasks, by making use of diagnostic information to increase routing efficiency and system throughput. The work will target systems possessing a relatively sparse interconnection structure such as grids, meshes, and hypercubes which constitute a large fraction of existing systems and are expected to dominate future applications. The proposed research will involve the integrated design of algorithms for diagnosis and routing, along with evaluations of algorithm performance that are both theoretical and experimental in nature. The theoretical work will utilize probabilistic analysis techniques in order to evaluate performance under recently proposed probabilistic models as well as to examine performance limits for these systems. The experimental work will involve the implementation and testing of the proposed algorithms on 32-node Intel IPSC/2 hypercube. A product of this research should be efficient algorithms for these fundamental problems in distributed fault tolerance that can be used in a wide range of multiprocessor/multicomputer systems.