分散環境に適応したアルゴリズムの提案

広瀬 依子 (0151088)


計算機の発明以来、単体でのデータ処理、端末からアクセスできる大型機へと進 歩し、現在では多くの独立した計算機がネットワークで結合された広域分散環境 へと発展してきた。またそれに伴い、広域分散環境で動作するソフトウェアに関 する研究が活発化している。

本論文では、このような広域分散環境で動作するソフトウェアについて、自律型 アルゴリズムの構成モデルを提案し、簡単な例題に適用して有効性を示す。

本モデルでは、各計算機は、近傍の計算機へメッセージを渡すことと、それに対 する返信を受けることしかしない。なお、ネットワークの不具合による影響を 避けて、自律的に終了判定をするため、タイムアウトにより終了するメカニズム を導入している。

このモデルを、最短経路問題、分散先の選択、単語変換に適用し、アルゴリズム が構成できることを示した。現状では小さな問題にしか適用できないが、本モデ ルはNP完全である巡回セールスマン問題にも適用できる。