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

分布式系统作为一种大规模、高安全性的应用系统， 应用程序，这些系统的容错成为一个关键 问题. 本研究的重点是诊断的基本问题 和容错路由。 这项工作将首次， 考虑协调这些重要任务，利用 诊断信息，以提高路由效率和系统 吞吐量 这项工作将针对拥有相对 稀疏互连结构，如网格、网格和超立方体 它们构成了现有系统的很大一部分， 预计将主导未来的应用。 拟议的研究将 涉及诊断和路由算法的集成设计， 沿着对算法性能的评估， 理论和实验性质的。 理论工作将 利用概率分析技术，以评估 最近提出的概率模型下的性能，以及 检查这些系统的性能限制。 试点工作 将涉及所提出的算法的实施和测试 在32节点Intel 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.