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

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

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