Construction of the distributed system with on-line localization

点击翻译按钮获取中文摘要

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