New theoretical basis of large scale dynamic distributed systems based on uncertain information and its applications

点击翻译按钮获取中文摘要

大規模動的ネットワークで動作する分散システムでは，各ノードが情報を収集する間にネットワーク環境が変動しうる．このため，各ノードが収集した大域情報は不確かさを伴う．そこで本研究では，不確かな大域情報を前提とする分散アルゴリズムの新たな理論的基盤の確立を目指す．これまでに，以下の課題に取り組み，一定の成果を得た．1．ノードが収集した大域情報の不確かさを反映した新たなモデルの提案：動的ネットワーク環境において，各ノードが利用可能な情報を局所的な情報に限定したモデルを提案した．2．大域タスクが実現できるために必要な大域情報の正確さの度合の解明：大域タスクを実現するには，各ノードにおいてどのような大域情報がどの程度の正確さで利用できればよいかの解明を目指した．訪問ノードで情報を収集し，得られた不確かな大域情報を利用してタスク処理を行うモバイルエージェントに関する研究を進めた．また，２次元平面上のモバイルロボット群の集合問題について，ロボットの視野に欠損がある場合のアルゴリズムに関する研究を進めた．3．大域情報の範囲や正確さの度合いが，大域タスクの達成可能な正確性や効率に及ぼす影響の解明：大域情報の範囲や正確さの度合いが，実現できる大域タスクの正確性や効率に与える影響の解明を目指した．動的ネットワークの一種である個体群プロトコルモデルに関する様々な研究を進めた．各個体が持つ情報量と大域性をうまく制限することにより，最も基本的かつ重要な問題であるリーダ選挙問題を超高速に解くアルゴリズムを開発した．4．不確かな大域情報を前提とする分散アルゴリズムの設計フレームワークの確立：動的ネットワークにおいて大域タスクを実現するフレームワークの基盤として，大域的あるいは局所的にいくつかのプロセスを選出する自己安定分散アルゴリズムに関する研究を進めた．