On the Stability of Huge-scale Distributed Systems - the Advent of the Era of Tera

与传统的分布式系统概念不同，通过分布式系统，我们指的是一个由自主代理组成的系统，这些代理可以通过一些通信设备相互通信，例如包括自主移动机器人系统，而不仅仅是计算机网络上通常的分布式系统。一些像WWW这样的大型分布式系统由几个giga代理组成，用tera来计算分布式系统大小的时代即将到来。本研究的目标是如此庞大的分布式系统。大型分布式系统的特征如下：首先，拓扑变化如此之快，以至于每个代理都无法忽略它；其次，与全局信息量相比，每个进程可以收集的本地信息量相对减少。研究的目的是建立系统稳定性和协议正确性的概念，并提出设计正确协议的方法，以保持给定分布式系统的稳定性。在下面，我们将这个研究项目的结果分为三组来解释。第一组包含关于大型分布式系统的概率搜索方法的论文。结果中的一个亮点是使用局部信息的随机漫步；这些随机游动达到了最优的命中时间，因此只要涉及命中时间，这些局部信息与全局信息一样强大。第二组是关于大型分布式系统稳定协议的论文。我们在其中一篇论文中引入了动态分布式系统的稳定化概念，并提出了一个稳定的令牌循环协议。第三部分收集了机器人系统中经常出现的平面搜索问题。请注意，发表列表中的论文选自2005年完成的作品。

Unlike the conventional concept of distributed system, by a distributed system, we mean a one consisting of autnomonous agents that can communicate with each other by some communication devices, including for example a system of autonomous mobile robots, not only usual distributed systems on computer networks. Some huge distributed system like WWW consists of several GIGAs of agents and the era that the size of a distributed system is counted by TERAs is just around the corner.Targets of this research are such huge distributed systems. The huge distributed systems can be characterized as follows ; first, the topology changes so rapid that each agent cannot ignore it, but second, the amount of local information that each process can collect relatively shrinks compared with the amount of global information.The objectives of the research are to establish the concepts of the stability of the system and the correctness of the protocol, and propose methods to design correct protocols to keep the stability of a given distributed system.In the following, we explain results of this research project by partitioning them into three groups. The first group contains papers on probabilistic search methods for huge distributed systems. A highlight among the results is about random walks using local information ; those random walks achieve the optimal hitting time and hence this local information is as powerful as the global information, as long as the hitting time is concerned.The second group consists of papers on stabilizing protocols for huge distributed systems. We in one of the papers introduced the concept of stabilization for dynamic distributed systems, and presented a stabilizing token circulation protocol. The third collects search problems on plane, which appears frequently in robot systems. Note that papers in the publication list are selected from the works done in 2005.