Distributed Algorithms for Implementing Highly Reliable Distributed Systems

用于实现高可靠分布式系统的分布式算法

• 批准号: 10205218
• 负责人: MASUZAWA Toshimitsu
• 金额: $ 6.46万
• 依托单位: Osaka University (2000-2001)Nara Institute of Science and Technology (1998-1999)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (B)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205218/
• 关键词: distributed algorithms; protocol; parallel algoritmhs; fault tolerance; self-stabilization; wait-freedom; computer cluster; 故障耐性

It is highly expected that distributed systems are designed and implemented on world-wide networks. However, the design of large scale of distributed systems is a very complicated task because of inherent autonomy of processes. Thus, it is strongly desired to establish effective paradigms for designing distributed systems.The aim of this research is to propose paradigms for designing distributed/parallel algorithms. Especially, we investigated the method for designing distributed/parallel algorithms that possess the property required for practical distributed systems. The subjects we addressed are summarized as follows :1. Distributed algorithm design for highly reliable/available distributed systems : We investigated self-stabilization and wait-freedom of distributed algorithms that are expected to be promising paradigms for designing practically reliable/available distributed systems.2. Distributed algorithm design for mobile computing : We investigated distributed algorithm design for distributed systems containing mobile computers, since mobile computers as PDAs (Personal Digital Assistants) become essential components of practical distributed systems.3. Parallel algorithm design for computer cluster systems : We investigated parallel algorithm design for distributed systems based on computer clusters, since computer clusters are practical platform of high performance distributed systems.

人们高度期望分布式系统在全球范围的网络上设计和实现。然而，由于进程固有的自治性，大规模分布式系统的设计是一项非常复杂的任务。因此，迫切需要建立有效的分布式系统设计范式，本研究的目的是提出设计分布式/并行算法的范式。特别是，我们研究了设计具有实际分布式系统所需的属性的分布式/并行算法的方法。本文主要研究内容如下：1.高可靠/可用分布式系统的分布式算法设计：我们研究了分布式算法的自稳定性和等待自由度，这些算法有望成为设计实际可靠/可用分布式系统的范例.移动的计算的分布式算法设计：我们研究了包含移动的计算机的分布式系统的分布式算法设计，因为作为PDA（个人数字助理）的移动的计算机成为实际分布式系统的重要组成部分.计算机集群系统的并行算法设计：由于计算机集群是高性能分布式系统的实用平台，我们研究了基于计算机集群的分布式系统的并行算法设计。

项目成果

Satoshige Ukena: "A Self-Stabilizing κ-Exclusion Protocol with κ-Wait-Freedom"電子情報通信学会技術研究報告書. COMP98-87. (1999)

Satoshige Ukena：“具有 κ-等待自由的自稳定 κ-排除协议”IEICE COMP98-87 (1999)。

Akihiro Fujiwara: "A cost optimal parallel algorithm for weighted distance transforms" Parallel computing. (採録決定). (1999)

Akihiro Fujiwara：“加权距离变换的成本最优并行算法”并行计算（已接受）。

石水 隆: "選択問題を解くBSPモデルおよびBSP$^*モデル上の並列アルゴリズム"電子情報通信学会論文誌(DI). J82-D-1. 533-542 (1999)

Takashi Ishimizu：“用于解决多项选择问题的 BSP 模型和 BSP$^* 模型上的并行算法”，电子、信息和通信工程师学会汇刊 (DI) J82-D-1 (1999)。

浮穴 学慈: "A self-stabilizing k-exclusion protocol with k-wait-freedom"電子情報通信学会技術研究報告. COMP98-8 7. 33-40 (1999)

Gakuji Ukie：“具有 k 等待自由的自稳定 k 排除协议”IEICE 技术报告 COMP98-8 7. 33-40 (1999)。

藤原 暁宏: "Practical parallelizability of some P-complete problems"電子情報通信学会技術研究報告. AL69-2. 9-16 (1999)

Akihiro Fujiwara：“一些 P 完全问题的实际并行性”IEICE 技术报告 9-16 (1999)。