分散アルゴリズム研究グループ紹介

Introduction to Distribute Algorithm Research and Development Group

分散アルゴリズム研究グループでは，よりよいネットワーク環境の実現のための理論的アプローチとして，分散アルゴリズムの研究・開発を行っています．

このページでは，本グループで行っている研究内容とともに，研究対象である分散アルゴリズムについても簡単に説明しています．以下の目次のリンクから，興味ある部分を選択して読んでください．手っ取り早く研究内容を知りたい方は， 4.から見ていただければ結構です．分散アルゴリズムがはじめての方は， 1.から順に読んでいただくことをお勧めします．内容的には，できるだけ平易な内容にとどめています．

目次

1. 分散アルゴリズムって？
2. 故障耐性のある分散アルゴリズム
3. 理論としての分散アルゴリズムの研究とは？
4. 具体的にどんな問題を考えているの？
5. 分散アルゴリズム研究グループの未来
6. 研究成果
   

1.分散アルゴリズムって？

分散アルゴリズムを一言で言うと，ネットワークにつながった計算機同士で，与えられた問題をどうやって解くかを規定するものです．もう少し定式化していうと，通信リンクで互いに接続されたプロセス同士が，情報を交換し協調しながら問題を解くためのアルゴリズムです．具体的な問題としては「リーダー選択問題」「相互排除問題」など，さまざまな問題が，さまざまなモデルの上で考えられています．

現実的にネットワークで利用されている分散アルゴリズムの例としては，インターネットの世界で古くから利用されている「RIP(Routing Information Protocol)」があげられます．これはBellman-Ford アルゴリズムといわれる距離ベクトル型ルーティングプロトコルで，さまざまな改良が加えられ，今日でも多くのネットワーク(主にLAN)で利用されています． IGRP(Interior Gateway Routing Protocol)も Bellman-Ford アルゴリズムを利用したルーティングプロトコルのひとつです．

2.故障耐性のある分散アルゴリズム

ネットワーク，中でもインターネットは，通信の確実性を強く保障するものではありません． したがって，ネットワークを利用したアプリケーションを使っているときでも，急にネットワークが切断されてしまい，それ以上仕事が進まなくなることは，多くの人が経験していることでしょう

ネットワークの切断(障害)と一口に言っても，さまざまな原因がありますが，大きく分けると次のふたつになるでしょう．

1. ネットワークに接続された計算機やルータの障害
2. ハブやケーブルを含めた通信路の障害

これらの障害は，分散アルゴリズムのモデル上では，それぞれプロセッサの故障，通信リンクの故障として扱います．そして，このような障害がおきても正しく問題を解くことができるアルゴリズムを「故障耐性のある分散アルゴリズム(fault tolerant distributed algorithm あるいは dependable distributed algorithm)」と呼びます．ネットワークが大規模になるにつれ，たった一箇所の障害が大規模な障害に発展する可能性が増大しています．そのような状況で，故障耐性のある分散アルゴリズムの開発が期待されています．

3.理論としての分散アルゴリズムの研究とは？

アルゴリズムというと，とかく理論的なものばかりが目に付き，実際の応用はあまり考慮されていないように考えられがちです (実際そういう側面がほとんどなのですが)．しかしRIPの例を見てもわかるように，分散アルゴリズムは，今日のネットワークを支える「基盤技術」の一つとして捉えられます．

一方，純粋に理論的な研究としての楽しみも十分にあります．理論的研究は，「出来上がり」としての「もの」を想像することが困難で，研究を進めていく上での目標が見えづらいという印象もあるでしょう．しかし，逆にとらえると，頭の中で純粋に思考のみで問題を解決し，結果を出すことも可能であることを意味します．実際，研究を始めて3ヶ月で結果を出し，論文に仕立て上げる人もいます．このような「アルゴリズムを思いつけばそれで成果」というのは，ある意味理論的研究の特権なのかもしれません．何せ，結果を出すまでに，早い人は早いのです．

しかし，みんながそんな簡単にはいきません(というか，普通は簡単ではないのです)．システムを構築しようとすると，まずはプログラミングの勉強，システム設計の手法，実現方法など，さまざまな知識を動員する必要があります．また，それらの知識を得るために，多くの時間が必要です．アルゴリズムも同じなのです．プログラミング言語を覚える代わりに，分散アルゴリズムが考えられているさまざまなモデルを勉強し，システム設計手法・実現方法を勉強する代わりに，今まで考えられてきた分散アルゴリズムの資産を学ばなければなりません．そのためにたくさんの論文を読み，議論・討論する必要があります．そういう土台ができて，初めて新たなアルゴリズムなりパラダイムなりが創造できるのです．

もちろん，理論的学習一辺倒では，よいアルゴリズムは生まれません．分散アルゴリズムはネットワーク上でその威力を発揮します．その土俵であるネットワークについての基礎知識も持っているに越したことはありません．そうして初めて，理論と実践に乖離のないモデルを構築し，分散アルゴリズムを設計することができるものと考えています．

そういう意味では，実践に強い理論的研究者が求められています．あなたはどうでしょう？

4.具体的にどんな問題を考えているの？

本研究グループでは，現在主に以下のような問題を考えています．

• ad-hoc ネットワークでのトークン巡回問題
  ad-hoc ネットワークとは，ネットワークに接続するために特別な設定が不要で，かつネットワークへの参加・退出が自由に行えるようなものです．つまり，ネットワーク中のノードやリンクが頻繁に出現・消滅するようなネットワークモデルです．このようなネットワーク中で，トークンを安全確実に巡回させるためのアルゴリズムを開発しています．
• モバイルエージェントの効率のよい巡回問題
  昨今，モバイルエージェントを用いたネットワークアプリケーションがさまざま提案・実現されつつあります．たとえば，モバイルエージェントを用いてネットワーク中に存在するさまざまな情報を収集しようとするとき，エージェントをどのような戦略で巡回させれば効率よく(すばやく・確実に) 収集できるでしょうか？そのような目的のための巡回アルゴリズムの開発を行っています．
• 自己安定アルゴリズム一般
  自己安定アルゴリズムとは，任意の一時故障(リンクやノードの一時的な停止，伝搬中のメッセージの内容改変など) にかかわらず問題を解くことのできるアルゴリズムで，非常に高度な故障耐性を持っています．現在知られている分散アルゴリズムの自己安定化を含めて，さまざまな問題に自己安定のパラダイムを適用し，高度な故障耐性を持つ分散アルゴリズムの開発を行っています．

上記の問題は，あくまでも一例です．本研究グループでは，最新の論文などの輪講を行い，常に分散アルゴリズムの可能性を探っています．その過程で，他にもさまざまな問題を扱うことになります．

また，本研究グループではアプリケーションの設計，開発についても考えています．

• 分散アルゴリズムの動きの可視化
  分散アルゴリズムは通信リンクで互いに接続されたプロセス同士が，情報を交換し協調し問題を解くので動作は複雑になります．動画などの教材を使用して分散アルゴリズムの動きを説明しますが，この様な教材を作成するのは手間がかかります．そこで，以下の様な教材の作成を補助するツールについて設計，開発を行っています．
  例えば，グラフ上で物が移動，変形する動画を作成することが可能な動画記述言語と動画生成エンジンを用いて，分散アルゴリズムの動きを示す動画を生成するツールを作成します.

5.分散アルゴリズム研究グループの未来

理論と実践のバランスが取れた研究を進めていくのが，ひとつの目標です．「分散アルゴリズムとは？」の中で述べている， Bellman-Ford のアルゴリズムは，理論的に考えられたアルゴリズムが実践で大いに利用されている，もっとも顕著な例でしょう．本研究グループでも，そんなアルゴリズムが開発できるといいな…と考えています．

もちろん，純粋に理論的な研究も同時に行っていきたいと考えています．むかしチューリング(Turing)が「チューリングマシン」を提案し，それは今でも計算機科学の基礎として利用し続けられています．そんな提案ができるとすばらしいですね．夢は「チューリング賞」でしょうか．「そんな大それた…」とはいえ，夢は大きく持っていたいものです．

研究成果

- 学術論文(full paper)

1. 片山喜章，長谷川敏之，高橋直久: "任意の単一リンク故障を考慮した生成木構成強安定プロトコル"， 電子情報通信学会論文誌，(Vol. J88-D-I,No.11), pp.1669-1678，(2005.11. )．
2. 宮永慎太郎，片山喜章，和田幸一，高橋直久，小林基成，森田正範，動的アドホックネットワークでの効率の良い統合・分離が可能な クラスタネットワーク構築アルゴリズム，電子情報通信学会論文誌，(Vol.J91-D，No.02)，pp.389-401，2008.2

- 学術論文(letter)

1. 佐々木敏晃，片山喜章，高橋直久: "グラフ上の動画作成を可能にする動画記述言語と動画生成エンジンの設計および実現"， FIT2004 情報技術レター，(LK-019)，pp.299-302，(2004.09.09)．

- 国際会議

1. Y. Katayama, T. Masuzawa, K. Wada: "Yet another self-stabilizing algorithm for load balancing on the rooted trees", Self-Stabilizing Distributed Systems Seminar (invited talk, @BIRS(Banff International Research Station), CANADA),(2004.10.06)．

- 国内研究会

1. 長谷川敏之，片山喜章，高橋直久: "経路情報を用いた生成木構成強安定プ ロトコルについて"，信学技法(COMP2003-92)，Vol.103, No.723， pp.49-56，(2004.03.16)(名工大)．
2. 中村友貴，片山喜章，高橋直久: "ノード及びリンク故障を考慮したエージェ ント巡回自己安定プロトコルについて"，信学技法(COMP2003-93)， Vol.103, No.723， pp.57-64，(2004.03.16)(名工大)．
3. 中村友貴，片山喜章，高橋直久: "木ネットワーク上でのトークン巡回故障封じ込め自己安定プロトコル"， 情報処理学会 アルゴリズム研究会 (2006-AL-104)，2005-AL-104(6)，pp.35--42, (2006.01.20)，(慶應義塾大学 矢上キャンパス)．
4. 宮永慎太郎，片山喜章，和田幸一，高橋直久，小林基成，森田正範: "効率の良い統合・分離が可能な動的クラスタネットワーク構築アルゴリズムについて"， 電子情報通信学会 コンピュテーション研究会(COMP2005-58)，信学技法，Vol.105， No.679， pp.9-16，(2006.03.22)，(電気通信大学)．
5. 宮永慎太郎，片山喜章，和田幸一，高橋直久，小林基成，森田正範: "WANET上でのクラスタ及び通信路構築自己安定アルゴリズムについて"， 情報処理学会 アルゴリズム研究会(AL111)，情処研報，Vol.2007， No.23， pp.9-16，(2007.03.09)，(鹿児島大学)．

- 全国大会等

1. 片山喜章，増澤利光，和田幸一: "木ネットワーク上での負荷分散自己安定 アルゴリズムについて"，2004年夏のL.A.シンポジウム，pp.11.1-11.6， (2004.07.15)(淡路島・夢舞台)．
2. 長谷川敏之，片山喜章，高橋直久: "生成木構成問題を解く強安定プロトコ ルに関する研究"，夏のL.A.シンポジウム(合歓の郷)，2003年夏のLAシンポ ジウム予稿集，pp. S7.1--S7.10，(2003.07.16)．

- ワークショップ

1. 佐々木敏晃，片山喜章，高橋直久: "背景と物体動作の連係方式を用いた動画生成システムの設計と実現"， 電子情報通信学会 第17回データ工学ワークショップ（DEWS2006），4B-i13，(2006.03.01-03)，（沖縄コンベンションセンター）．

- 修士論文・卒業論文

1. 長谷川敏之："経路情報を用いた生成木構成強安定プロトコルに関する研究"， 平成15年度修士論文
2. 佐々木敏晃："汎用的動画生成エンジンの実現と分散アルゴリズムアニメーション作成ツールへの適用", 平成15年度卒業論文
3. 中村友貴："ノードの消滅を考慮したモバイルエージェント巡回自己安定プロトコルに関する研究", 平成15年度卒業論文
4. 佐々木敏晃："時空間制御機能を有する動画生成システムに関する研究", 平成17年度修士論文
5. 中村友貴："木ネットワーク上でのトークン巡回故障封じ込め自己安定プロトコルに関する研究", 平成17年修士論文
6. 宮永慎太郎： "効率の良い統合・分離が可能な動的クラスタネットワーク構築アルゴリズムに関する研究", 平成17年度卒業論文
7. 宮永慎太郎："WANET上でのクラスタ及び通信路構築自己安定アルゴリズムに関する研究", 平成19年度修士論文