Construction of the distributed system with on-line localization

在线本地化分布式系统构建

• 批准号: 11680367
• 负责人: YOSHIDA Noriyoshi
• 金额: $ 1.92万
• 依托单位: Hiroshima City University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1999
• 资助国家: 日本
• 起止时间: 1999 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-11680367/
• 关键词: distributed systems; on-line algorithms; routing problem; load balancing; scheduling problem; local algorithm; consensus problem; data mining

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

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

项目成果

田中,大谷,齊藤,上土井,吉田: "分散環境でのオンラインルーティング・スケジューリング手法の実験的考察"電子情報通信学会技術研究報告. IN2000-145. 73-78 (2000)

Tanaka、Otani、Saito、Kamidoi、Yoshida：“分布式环境中在线路由和调度方法的实验研究”IEICE 技术报告 IN2000-145 (2000)。

松浦、上土井、吉田: "競合を考慮した合意問題に対する共有メモリアルゴリズム"2000年IEEE広島学生シンポジウム論文集. 162-162 (2000)

Matsuura、Kamidoi、Yoshida：“考虑竞争的共识问题的共享内存算法”2000 年 IEEE 广岛学生研讨会论文集 162-162 (2000)。

松浦,上土井,吉田: "競合を考慮した合意問題に対する共有メモリアルゴリズム"2000年IEEE広島学生シンポジウム論文集. 162 (2000)

Matsuura、Kamidoi、Yoshida：“考虑竞争的共识问题的共享内存算法”2000 年 IEEE 广岛学生研讨会论文集 162 (2000)。

T.Saitoh, J.Ohtani, Y.Kamidoi and N.Yoshida: "Efficient on-line algorithms for the load balancing problem"Technical report of IEICE. COMP99-08. 25-32 (2000)

T.Saitoh、J.Ohtani、Y.Kamidoi 和 N.Yoshida：“负载均衡问题的高效在线算法”IEICE 的技术报告。

Y.Kamidoi,S.Wakabayashi,N.Yoshida: "A divide conquer approach to the minimum k-way cut problem"Algorithmica(Springer). accepted.

Y.Kamidoi、S.Wakabayashi、N.Yoshida：“最小 k 路切割问题的分治方法”Algorithmica（Springer）。