Construction of the distributed system with on-line localization

为了提高分布式网络系统的性能和可靠性，保持分布式网络系统在线运行时的可扩展性，我们对分布式系统进行了以下五个子课题的研究。在线路由调度算法的发展调度问题和路由问题都是分布式系统中负载平衡的重要问题。一般来说，调度问题和路由问题是分开处理的。提出了一种以最小化通信和处理负荷为目标的在线路由调度算法。在我们的实验结果中，所提出的算法优于将调度问题和路由问题分开处理的方法。无等待共识的共享内存争用算法研究共识可以看作是分布式系统中的一种通用协议方案。共识问题是在一组流程上定义的。每个进程都有一个初始值，未失败的进程必须确定一个共同的值，该值是其中一个进程的初始值。在解决共识问题时存在一个争论问题。争用严重影响协议的性能。为了降低争用代价，我们提出了一种新的无等待共识算法。在线路由调度算法应用的问题考虑在线路由调度算法应用的两个重要问题(1)和(2)。(1)有限时长呼叫在线准入控制算法的实验评价。在网络系统中，在线接收控制问题是在不降低服务质量的前提下决定是否接受新呼叫。由于持续时间未知的情况非常自然且具有实际重要性，我们考虑了在线录取控制问题，以最小化有限持续时间呼叫的拒绝率。提出了一种新的在线准入控制算法。(2)网络分区算法的发展。为了将所提出的在线算法作为局部方法来实现，将一个网络划分为若干个子网络。我们用图划分模型来分析这个网络划分问题。在此基础上，提出了一种快速的网络分区算法。当前，实际系统中的数据库和网络上的分布式数据库越来越大规模，并且具有高容量。因此，在这些应用领域中，采用复杂过程的数据挖掘技术已不再具有实用性。本文提出了一种基于最近邻图的聚类算法和一种基于数据结构简单的固定网格聚类算法。然后，从定位的角度对这些方法的性能进行了实验研究。故障检测器异步共享内存算法的开发先前的故障检测器算法通过发送和接收消息来检测故障，给定进程的每个任务的处理时间和消息到达时间的限制。当该算法应用于一个完美的异步系统时，延迟过程可以被判定为失败。我们提出了一种故障检测器的共享内存算法，该算法在全异步系统中，所有非故障进程组成一个共享故障列表。少

In order to improve the performance and the reliability and to maintain the scalability of distributed network systems in on-line operation, we study on distributed systems for the following five subprojects.1. Development of on-line routing-scheduling algorithmsBoth the scheduling problem and the routing problem are important problems for load-balancing in distributed systems. In general, the scheduling problem and the routing problem were dealt with separately so far. We proposed algorithms to solve an on-line routing-scheduling problem which aims to minimize the load of both communication and processing. In our experimental results, proposed algorithms outperform the previous method, in which the scheduling problem and the routing problem were treated separately.2. Study on contention in shared memory algorithms for wait-free consensusConsensus can be viewed as a general scheme of agreement in a distributed system. The consensus problem is defined over a set of processes. Each proce … More ss has an initial value and non-failed processes have to decide on a common value that is the initial value of one of the processes. There is a contention problem in solving a consensus problem. Contention influence the performance of protocol heavily. We proposed a new wait-free consensus algorithm in order to reduce the contention cost.3. Consideration to issues for the application of the on-line routing scheduling algorithmWe considered two important following issues (1) and (2) for the application of the on-line routing scheduling algorithm. (1) Experimental evaluation of on-line admission control algorithms for limited duration calls. On network systems, the on-line admission control problem is to decide whether or not to accept the new call without lowering a quality of service. Since the case of unknown durations is quite natural and practical importance, we considered the problem of on-line admission control to minimimze the rejected rate of limited duration calls. A new algorithm for the on-line admission control problem was proposed. (2) The development of the network partitioning algorithm. For the implementation of the proposed on-line algorithm as the local method, a network is divided into several sub-networks. We analysised this network partitioning problem as graph partitioning models. And based on our analysis, we proposed a fast network partitioning algorithm.4. Experimental evaluation of data mining techniques from the viewpoint of the localizationRecently, databases in practical systems and distributed data repositories on the network become more and more large-scale, and have high-capacity. Therefore, in these application areas, the data mining techniques by complex procedure have not been practical any more. We proposed a constructing method of a κ-nearest neighbor graph and a clustering algorithm used a fixed-grid method which is a simple data structure. Then, we studied the performance of these methods experimentally from the viewpoint of the localization for these techniques.5. Development of an asynchronous shared memory algorithm for failure detectorThe previous failure detector algorithms detect failures by sending and receiving messages, given the restriction for the processing time to each task of processes and the arrival time of the messages. When the algorithm is applied in a perfect asynchronous system, the delaying process may be judged as a failure. We proposed a shared memory algorithm for failure detector by which all non-failed processes compose a shared failure-list in a totally asynchronous system. Less