Algorithm Engineering for Wide Area Distributed Systems

分布式系统由许多自主工作的Agent（如计算机、进程、车辆等）组成，为了使系统具有灵活性和可扩展性，它不采用主从式的控制机制，Agent只根据自己的初始信息和与邻居Agent通信获得的局部信息，以异步方式决定自己的行为。在这个项目中，我们在许多领域的成果，从自主移动的机器人到并行编译器，其中一些结果在下面列出和解释：（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