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

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

• 批准号: 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はポイント競合度である。

我们对分布式共享内存环境中无等待性能的分布式算法的设计进行了研究。无等待性是指当一个进程按照某种算法执行某些处理时，它可以在有限的步骤内完成该处理，而不管其他进程的运行速度如何。非等待算法具有有效协调在不同类型的计算机上运行的具有不同处理能力的进程的理想特性，并且能够抵抗进程停止故障。今年我们对非等待算法中的点竞争级自适应算法进行了研究。点竞争自适应算法是一种算法的时间复杂度仅取决于同时活动进程的数量的算法，并且是理想的，因为它可以在只有少量进程竞争的情况下有效地找到解决方案。财产。在本研究中，我们提出了一种点竞争自适应算法来解决迭代重命名问题。到目前为止，我们针对命名空间 k(2k-1) 的重复重命名问题提出了一种在时间和空间复杂度方面优于已知算法的算法。其中，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)。