Algorithm Engineering for Wide Area Distributed Systems

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

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