A04班 「並列／分散アルゴリズム」の紹介
A04班は並列／分散アルゴリズムをテーマにしている。
大規模な問題を効率良く解くことは計算機科学が目指す
最も明白な目的の一つである。この目的を解決する一つの方法として、
大規模な並列処理や分散処理が必要とされ、これらの分野の研究は盛んに
行われている。しかしながら、分散システムでは非同期アルゴリズムに関する問題、
耐故障性通信アルゴリズム、情報セキュリティの問題など手強い問題も多い。
また、大規模な計算機ネットワーク上で実現されるサイバースペースを維持管理
するためのソフトウエアに関する基本的なアルゴリズム、モバイル分散システム上
の情報処理や情報伝達に関するアルゴリズムなどもこれらの分野の重要な問題である。
これらの重要な問題を解決するために、しっかりした理論に基づく方法論の確立
および実用的かつ有効なアルゴリズムの設計を各研究グループ毎に行っている。
また、PVM(Parallel Virtual Machine)上で作成したアルゴリズムを大学間で動作
させることを目標に A04 班全体で情報交換を行っている。
A04班は六つの研究グループから成り、研究代表者と研究分担者を合わせて
総勢23名で構成されている。以下に各グループを紹介する。
研究課題 分散ネットワークにおける情報通信の安全性に関する研究
研究代表者： 五十嵐 善英 （群馬大学工学部情報工学科、A04 班班長） 研究分担者： 西谷 泰昭 （岩手大学工学部情報システム工学科） 大澤 新吾 （群馬大学工学部情報工学科） 茂木 和弘 （群馬大学工学部情報工学科）
研究内容 本研究の目的は分散システムにおける信頼性、安全性、 機密性の高い通信プロトコルや分散アルゴリズムの設計 と効率解析である。特にマルチパーティ計算の安全性、 共有メモリータイプ分散アルゴリズムの競合問題および 故障耐性、大規模並列/分散計算の高速化などの研究を 行なっている。 また、アルゴリズムのデータベース化の一環として、 有限群上の離散対数問題を解くアルゴリズムの一つである Pohlig-Hellman の アルゴリズムを PVM 上で実装などを行っている。
研究課題 適応化と確率化による高速ラウティングアルゴリズムの開発
研究代表者： 岩間 一雄 （京都大学大学院情報学研究科） 研究分担者： 岡部 寿男 （京都大学大学院情報学研究科） 宮崎 修一 （京都大学大学院情報学研究科） 岩本 宙造 （広島大学工学部） 川久保 和雄 （福山大学工学部情報処理工学科）
研究内容 n2個のプロセッサが2次元メッシュ状に接続された計算機
モデル上でのパケットラウティング問題を取り扱っている．ラ
ウティング時間の下限は自明な2n-2が知られている．すべて
のパケットのラウティング経路をあらかじめ固定した場合，ラ
ウティング時間の上限は我々の出した3456n時間が最良であっ
た．本研究ではをこの上限を
に改良した．
ここで，
は任意の正定数であり，各プロセッサのキュー
サイズはの関数である．また，最近では，CNF充足可
能性問題に対する局所探索アルゴリズムを並列・分散環境で並
列実行させることにより高速化し，困難なベンチマーク例題や
実世界組合せ問題を高速に解けることを示した．
研究課題 計算困難な問題を利用した公開鍵暗号アルゴリズムの設計とその解析
研究代表者： 櫻井 幸一 （九州大学大学院システム情報科学研究科、A04班班長） 研究分担者： 岡本 龍明 （NTT 研究所）
研究内容 岡本が中心となって、 日本応用数理学会 「数論アルゴリズムとその応用」研究部会 （ 代表者： 中村 憲@東京都立大学）が７月に発足した。 この第一回研究集会が7月21日、日本大学理工学部で開催された。 参加者は100名ほどであり、数学、数論アルゴリズム、暗号理論 の各方面の研究者が集まり、活発な議論が行なわれた。 櫻井も、"On Recent results on two major number-theoretic problems in public-key cryptography: Factoring vs. RSA" and Discrete Log. vs. Diffie-Hellman"と題した 本研究プロジェクトに関わる発表を行なった。
研究課題 高度な信頼性を有する大規模分散システム構築のための分散アルゴリズムに関する研究
研究代表者： 増澤 利光 （奈良先端科学技術大学院大学情報科学研究科） 研究分担者： 井上 美智子 （奈良先端科学技術大学院大学情報科学研究科） 片山 喜章 （奈良先端科学技術大学院大学情報科学センター） 藤原 暁宏 （九州工業大学情報工学部電子情報工学科）
研究内容 高度な信頼性を有する大規模分散システムを実現するための並列・分散アルゴリズムの 設計を行っている．特に，停止故障に対する高度な故障耐性を有する 無待機分散アルゴリズム（他の計算機の動作を待つことなく，各計算機が解を求める）と， 一時故障に対する高度な故障耐性を有する自己安定分散アルゴリズム（どのようなネット ワーク状況から実行を開始しても解を求める）について研究している．モバイル 分散システムも対象としている．また，並列・分散化による高速処理を実現するた めに，ワークステーション群からなる分散処理システムにおける並列アルゴリズムの 設計を行っている．さらに，並列化による高速化が困難であるＰ完全問題に対し， 実際的な規模（計算機数）の分散処理システムで最適加速を実現する並列アルゴリズムの 設計を行っている．
研究課題 広域分散システムのためのアルゴリズム工学
研究代表者：山下 雅史 （九州大学大学院システム情報科学研究科） 研究分担者： 藤田 聡 （広島大学工学部） 宮野 英次 （九州芸術工科大学芸術工学部） 朝廣 雄一 （九州大学大学院システム情報科学研究科）
研究内容 広域分散システムのためのアルゴリズム工学という研究題目のもとで,
昨年度から特に強力に推進している話題に, 分散メタヒューリスティックの研究があり, 分散メタヒューリスティックを実際の計算機クラスタ上に実現し, サイズが大きくて従来はなかなか計算できなかった 計算困難問題を具体的に解くことを目指している. そのために, (1)逐次メタヒューリスティックアルゴリズムの分散化とその計算機クラスタ 上での実現と, (2)負化分散アルゴリズムや自律的故障回復アルゴリズムなど, 高性能計算機クラスタの設計技術の検討を行ない, 第３回テーマ別研究会などでその成果を発表した.
研究課題 並列アルゴリズムに対する設計パラダイムと理論モデルの実現可能性に関する研究
研究代表者： 和田 幸一 （名古屋工業大学電気情報工学科） 研究分担者： 陳 慰 （名古屋工業大学電気情報工学科） 中野 浩嗣 （名古屋工業大学電気情報工学科） 伊藤 暢浩 （名古屋工業大学電気情報工学科）
研究内容
並列アルゴリズムに関しては、P-完全問題である凸包層問題と エンベロープ層問題に対して現実的な意味で効率的な並列アルゴリズムを 与えた．特に、凸包層問題に対してはコスト最適で最適な高速化ができる アルゴリズムを与えた．また、並列アルゴリズム設計法として、 多レベル分割統治法を提案し、いくつかの基本的問題に対して 効果的であることを実証した．
分散アルゴリズムに関しては、計算機網に対する耐故障性の高いルーティング アルゴリズム、 無線ネットワークに対するリーダ選択、初期化、ルーティング、 ランキング、ソーティングなどを行なう効率よいアルゴリズムを示した． また、不完全情報を取り扱うマルチエージェントモデルを構築し、 マルチエージェントシステムのベンチマークとしても知られ るサッカーエージェントとして実装し、有効性を確認した．