巨大分散システムの安定性-テラの時代に向けて
【研究分野】計算機科学
【研究キーワード】
巨大分散システム / 安定性 / 確率的手法 / 大域情報 / 局所情報 / 分散アルゴリズム / 統計力学的手法 / ランダムウォーク / 自己安定システム / ランダムウォー
【研究成果の概要】
WWWのようなソフトウェアシステムばかりでなく,たとえば群ロボットシステムのような自律分散機械システムなどを含めて,通信機能を有する複数のエージェントから構成されるシステムを広く分散システムと呼ぶ.分散システムのエージェント数は既にギガで測られる時代にあり,テラの時代が近づきつつある.本研究が検討の対象とするのはこのような巨大な分散システムである.巨大分散システムは,エージェント数が巨大であるという理由から,1)各エージェントが無視できない程度にシステムの動的な変化が大きくなるにも関わらず,2)各エージェントが収集可能な局所情報が大域情報に占める割合は相対的に小さくなるという特徴を持つ.
当初の研究目的として以下の2つを掲げた.第1の目的は,巨大分散システムにおける計算の「正当性」や「安定性」といった概念を確立することである.第2の目的は,確立された安定性の概念のもとで,安定なアルゴリズムを構築するための手法を確立し,いくつかの具体的で基本的な問題に対して,具体的に安定なアルゴリズムを構築することである.
研究成果を3つのグループに分け,それぞれを簡単に紹介する.第1のグループは,巨大分散システムにおける確率的探索手法の研究である.巨大分散システムの制御に乱歩が有効であることを示した.従来は,標準的乱歩だけが用いられていたが,与えられた問題に対して適切な乱歩を設計する問題を新たに提起し,ある問題に対して,設計が可能であることを示した.第2にグループは巨大分散システムの安定性に関する研究であり,安定性の概念を検討するとともに,安定なプロトコルを設計した.第3のグループは平面上の動的問題の研究であり,平面上の探索問題を主に取り扱った.なお,裏面の成果リストには主な最終年度の成果を表示した.
【研究代表者】