Distributed Algorithms for Implementing Highly Reliable Distributed Systems

人们对分布式系统的设计和实现寄予了很高的期望，这些系统都是在全球网络上设计和实现的。然而，由于进程本身的自主性，大规模分布式系统的设计是一项非常复杂的任务。因此，迫切需要建立用于设计分布式系统的有效范例。本研究的目的是提出用于设计分布式/并行算法的范例。特别是，我们研究了设计具有实际分布式系统所需特性的分布式/并行算法的方法。主要研究内容如下：1.高可靠/可用分布式系统的分布式算法设计：我们研究了分布式算法的自稳定和无等待问题，这些算法有望成为设计实际可靠/可用分布式系统的范例。面向移动计算的分布式算法设计：由于移动计算机作为PDA(Personal Digital Assistant，个人数字助理)已经成为实际分布式系统的重要组成部分，我们研究了包含移动计算机的分布式系统的分布式算法设计。计算机集群系统的并行算法设计：由于计算机集群是高性能分布式系统的实用平台，我们研究了基于计算机集群的分布式系统的并行算法设计。

It is highly expected that distributed systems are designed and implemented on world-wide networks. However, the design of large scale of distributed systems is a very complicated task because of inherent autonomy of processes. Thus, it is strongly desired to establish effective paradigms for designing distributed systems.The aim of this research is to propose paradigms for designing distributed/parallel algorithms. Especially, we investigated the method for designing distributed/parallel algorithms that possess the property required for practical distributed systems. The subjects we addressed are summarized as follows :1. Distributed algorithm design for highly reliable/available distributed systems : We investigated self-stabilization and wait-freedom of distributed algorithms that are expected to be promising paradigms for designing practically reliable/available distributed systems.2. Distributed algorithm design for mobile computing : We investigated distributed algorithm design for distributed systems containing mobile computers, since mobile computers as PDAs (Personal Digital Assistants) become essential components of practical distributed systems.3. Parallel algorithm design for computer cluster systems : We investigated parallel algorithm design for distributed systems based on computer clusters, since computer clusters are practical platform of high performance distributed systems.