自律分散システムにおける大域情報と局所情報

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

互いに通信しながら自律的に動作するプロセス集合を分散システムと呼ぶ.プロセスは逐次プログラムの実行をモデル化したものであるが,分散システムの定義を少し拡張し,プロセスを自律的な計算主体と定義することで分散ロボットシステムや社会システムなども分散システムの範囲に入れることができる.分散アルゴリズム設計の基本的な困難さは局所情報を用いて大域的に矛盾のない判断を下さなければならないところにあり,従って,分散アルゴリズム研究の本質が大域情報と局所情報の関わりを研究する所にある.12年度に開始され今年度に最終年度を向かえた本萌芽研究の目指す所はその解明にあった.過去2年間の成果はそれぞれの年度の実績報告書に報告したが,本年度は,それらに,以下で説明する素晴らしい発見を付け加えることができた.グラフ上のランダムウォークは分散アルゴリズムばかりでなく様々な領域で用いられている基本概念の一つである.分散アルゴリズムの領域に限っても,インターネットのWEB探索やアドホックネットワークの通信など多彩な応用が報告されている.これらの応用では,その効率はヒッティング時間に依存する.グラフの頂点数をnとすると,通常のランダムウォークのヒッティング時間はO(n^∧3)であるが,隣接ノードの情報を利用することによりヒッティング時間がO(n^∧2)に減少でき,しかも,最悪の場合には,(大域情報も含めて)これ以上の情報はヒッティング時間の減少には寄与しないことを示した.