Algorithm Engineering for Wide Area Distributed Systems

分布式系统由许多自主工作的代理组成，如计算机、进程、交通工具等。为了使系统具有灵活性和可扩展性，它没有采用主从式控制整个代理的机制，因此代理只根据自己的初始信息和通过与邻居代理通信获得的本地信息来异步地决定自己的行为。在这个项目中，我们在从自主移动机器人到并行编译器的许多领域都取得了成果，其中一些成果列举并解释如下：(A)分布式算法理论：设计分布式算法的一个困难来自一个共同的需求：它需要在给定局部信息的情况下决定全局一致的行为。另一方面，分布式算法的优劣衡量标准是为解决所考虑的问题而交换所需的信息量。因此，我们调查了…解决特定问题需要交换更多的信息量，并采用最优的信息分配方式来减少必要的信息交换量。(B)分布式算法的设计：对于一些问题，我们设计分布式算法。首先，对于互斥问题这一基本的同步问题，我们设计了一种容错算法，该算法可以容忍任意数量的暂态故障，称为自稳定算法。接下来，我们研究了广义分配问题。这是一个在现实世界中有许多实际应用的问题。然而，这是一个NP完全问题，因此我们设计了一种基于局部搜索范式的序列启发式算法并行化得到的簇处理算法，其目的是在实际的时间约束下获得足够好的解。自主移动机器人系统：研究了自主移动机器人系统的分布式控制问题。特别是，我们研究了一组机器人搬运物体的问题，设计了一种分布式控制算法，并对其性能进行了评估。较少

A distributed system consists of many autonomously working agents like computers, processes, vehicles, and so on. For making the system flexible and extendible, it does not adopt a mechanism to control the whole agents in the master-slave fashion, and hence the agents decide their behaviours in an asynchronous manner depending only on their initial information and local information they obtained by communication with their neighbor agents. In this project, we have results in many fields from autonomous mobile robots to parallelized compilers, some of which results are listed and explained in the following :(A)Theory of Distributed Algorithms : A difficulty of designing a distributed algorithm comes from a common requirement : it is required to decide a globally consistent behavior, given local information. On the other hand, a goodness measure of distributed algorithms is the amount of information necessary to exchange to solve a problem under consideration. Hence, we investigated the … More amount of information necessary to exchange to solve a particular problem, and an optimal way of information allocation to reduce the amount of necessary information exchange.(B) Design of Distributed Algorithms : For some problems, we design distributed algorithms. First of all, for the mutual exclusion problem, which is a basic synchronization problem, we design a fault tolerant algorithm that tolerates any number of transient faults called a self-stabilisation algorithm. Next, we investigate the generalized allocation problem. It is a problem that has many practical applications in real-world. However, it is known as a NP complete problem, so we design a cluster processing algorithm which is obtained by parallelize a sequencial heuristic algorithm based on the local search paradigm, the aim of which is to get a sufficiently good solution in a practical time contraint. We then evaluate its performance.(C) Autonomous Mobile Robot System : We investigated a distributed control problem for autonomous mobile robot systems. In particular, we investigated the problem of carrying an object by a group of robots, designed a distributed control algorithm, and then evaluated it performance. Less