分散共有メモリ環境において故障耐性を考慮した効率のよい分散アルゴリズムの設計

分布式共享内存环境下考虑容错的高效分布式算法设计

• 批准号: 12780225
• 负责人: 井上 美智子
• 金额: $ 1.15万
• 依托单位: Nara Institute of Science and Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-12780225/
• 关键词: 分散アルゴリズム; 共有メモリシステム; ポイント競合度適応; 繰り返し改名問題; 無待機アルゴリズム; 無待機性; 自己安定性; 故障耐性

分散共有メモリ環境において、無待機性を有する分散アルゴリズムの設計に関して研究を行なた。無待機性とは、プロセスがアルゴリズムに従ってなんらかの処理を行なう時、他のプロセスの動作速度に関わらず有限回のステップで処理を完了できるという性質である。無待機なアルゴリズムは、異種多様な計算機上で動作する処理能力の異なるプロセスをそれぞれ効率良く協調させる、プロセスの停止故障に耐性があるといった望ましい性質をもつ。本年度は、無待機アルゴリズムの中でも、ポイント競合度適応型アルゴリズムに関して研究を行った。ポイント競合度適応型アルゴリズムとは、アルゴリズムの時間複雑度が、同時にアクティブであるプロセス数にのみ依存するアルゴリズムであり、少数プロセスのみが競合するような状況では効率よく解を求めることができるといった望ましい性質を持つ。本研究では、繰り返し改名問題を解くポイント競合度適応型アルゴリズムを提案した。これまで、名前空間k(2k-1)である繰り返し改名問題に対し、時間計算量、空間計算量がともに既知めアルゴリズムより優れたアルゴリズムを提案した。ここで、kはポイント競合度である。

Research on the design of decentralized shared environment with no standby No waiting time, no waiting time, no waiting No waiting time, no waiting time. This year, there is no research on the relationship between standby and competition. The time complexity of the system is different, and the time complexity of the system is different, and the time complexity of the system is different, and the time complexity of the system is different. This paper presents a proposal for solving the problem of changing the name of a project. The space k(2k-1) before the name is changed to the name of the problem, the amount of time calculated, the amount of space calculated, the amount of time calculated.ここで、kはポイント竞合度である。

项目成果

Michiko Inoue, Shinya Umetani, Toshimitsu Masuzawa, Hideo Fujiwara: "Adaptive Long-Lived O(k^2)-Renaming with O(k^2)Steps"Proceedings of the 15th International Symposium on Distributed Computing. 123-135 (2001)

Michiko Inoue、Shinya Umetani、Toshimitsu Masuzawa、Hideo Fujiwara：“自适应长寿命 O(k^2)-用 O(k^2)Steps 重命名”第 15 届分布式计算国际研讨会论文集。

Hiroyoshi Matsui: "Fault-Tolerant and Self-Stabilizing Protocols using an Unreliable Failure Detector"IEICE Transactions on Information and Systems. Vol.E83-D,No.10. 1832-1840 (2000)

Hiroyoshi Matsui：“使用不可靠故障检测器的容错和自稳定协议”IEICE Transactions on Information and Systems。

Sen Moriya: "Wait-Free Linearizable Distributed Shared Memory"IEICE Transactions on Information and Systems. Vol.E83-D,No.8. 1611-1621 (2000)

Sen Moriya：“无等待线性化分布式共享内存”IEICE Transactions on Information and Systems。

谷口博人: "アドホックネットワークにおけるクラスタ構成法"電子情報通信学会論文誌(D1). Vol.J84-D-1,No.2. 127-135 (2001)

Hiroto Taniguchi：“自组织网络中的集群配置方法”，电子、信息和通信工程师学会会刊（D1），第 127-135 卷（2001 年）。

Shinya Umetani, Michiko Inoue, Toshimitsu Masuzawa, Hideo Fujiwara: "Adaptive Long-lived Renaming Algorithm in the asynchronous shared memory"情報処理学会研究報告2001-AL-80-9. 59-66 (2001)

Shinya Umetani、Michiko Inoue、Toshimitsu Masuzawa、Hideo Fujiwara：“异步共享内存中的自适应长寿命重命名算法”日本信息处理学会研究报告 2001-AL-​​80-9 (2001)。