• Introduction to Distribute Algorithm Research and Development Group

研究紹介 目次

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

研究成果

1. 学術論文(full paper)
2. 学術論文(letter)
3. 国際会議
4. 国内研究会
5. 全国大会等
6. 修士論文・卒業論文
7. 受賞等 QualNet Network Simulator

ごあいさつ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

研究紹介へ

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

研究成果

- 学術論文(full paper)

1. Yonghwan Kim, Haruka Ohno, Yoshiaki Katayama and Toshimitsu Masuzawa, "A Self-Stabilizing Algorithm for Constructing a Maximal (1,1)-Directed Acyclic Mixed Graph", International Journal of Networking and Computing, Vol. 8, No.1, pp.53-72, (2018.01.).
2. Yonghwan Kim and Yoshiaki Katayama, "A Self-optimizing Routing Algorithm using Local Infor- mation in a 3-dimensional Virtual Grid Network with Theoretical and Practical Analysis", International Journal of Networking and Computing, Vol. 7, No. 2, pp. 349-371, (2017.07.).
3. 宮永慎太郎，片山喜章，和田幸一，高橋直久，小林基成，森田正範，動的アドホックネットワークでの効率の良い統合・分離が可能な クラスタネットワーク構築アルゴリズム，電子情報通信学会論文誌，(Vol.J91-D，No.02)，pp.389-401，2008.2
4. 片山喜章，長谷川敏之，高橋直久: "任意の単一リンク故障を考慮した生成木構成強安定プロトコル"， 電子情報通信学会論文誌，(Vol. J88-D-I,No.11), pp.1669-1678，(2005.11.)．

- 学術論文(letter)

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

- 国際会議

1. Ryo Yahagi, Yonghwan Kim and Yoshiaki Katayama, "A Parallel Branch-and-Bound Method using MapReduce and HBase", The 22nd Korea-Japan Joint Workshop on Algorithms and Computaion(2019.9).
2. Yusuke Sawada, Yonghwan Kim and Yoshiaki Katayama, "A Self-optimizing Three Nodes Routing Algorithm based on local information in Virtual Grid Networks", The 22nd Korea-Japan Joint Workshop on Algorithms and Computaion(2019.9).
3. Yonghwan Kim, Junya Nakamura, Yoshiaki Katayama and Toshimitsu Masuzawa, "A Cooperative Partial Snapshot Algorithm for Checkpoint-Rollback Recovery of Large-Scale and Dynamic Distributed Systems", 10th International Workshop on Parallel and Distributed Algorithms and Applications, (2018.11.).
4. Yonghwan Kim, Hiroki Aono, Yoshiaki Katayama and Toshimitsu Masuzawa, "A Self-Stabilizing Algorithm for Constructing a Maximal (2,2)-Directed Acyclic Mixed Graph", Proceedings of the Sixth International Symposium on Computer and Networking (CANDAR 2018), (2018.11.).
5. Yonghwan Kim, "An Autonomous Distributed System Consisting of Pair-Robots: Model and Basic Algorithms", Invited Talk, 2nd Workshop on Self-organization in Swarm of Robots, (2018.11.).
6. Yonghwan Kim, Yoshiaki Katayama and Toshimitsu Masuzawa, "An Introduction to A (s,t)-Directed Acyclic Mixed Graph (DAMG) and Maxi- mal (s,t)-DAMG Construc- tions When s ＜= 2 and t ＜=2", Proceedings of the 20th Korea-Japan Joint Workshop on Algorithms and Computation (WAAC2017), (2017.08.).
7. Yonghwan Kim, Haruka Ohno, Yoshiaki Katayama and Toshimitsu Masuzawa, "A Self-Stabilizing Algorithm for Constructing (1,1)-Maximal Directed Acyclic Graph", Proceedings of the 2017 IEEE International Parallel and Distributed Processing Symposium Workshops, (2017.08).
8. Yonghwan Kim and Yoshiaki Katayama, "A Self-optimizing Routing Algorithm in a 3-dimension- al Virtual Grid Network", Proceedings of the Fourth International Symposium on Computer and Networking, (2016.11.).
9. Rentaro Watanabe, Yonghwan Kim, Fukuhito Ooshita, Hirotsugu Kakugawa and Toshimitsu Masuzawa, "Realization of An Efficient Concurrent Partial Snapshot Algorithm for Large-scale and Dynamic Distributed Systems", The 5th International Workshop on Networking, Computing, Systems, and Software, (2015.12.).
10. 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. 大藪匡記，金鎔煥，片山喜章, "二次元三角格子平面における7台の自律分散ロボットによる集合について", 電子情報通信学会技術研究報告コンピュテーション(COMP), vol.118, (2019.03.).
2. 青野宏紀，金鎔煥，片山喜章, "2連結無向グラフにおける強連結(2,2)-DAG構成アルゴリズムについて", 電子情報通信学会技術研究報告コンピュテーション(COMP), vol.118, (2019.03.).
3. 長尾英剛，金鎔煥，片山喜章，和田幸一, "三次元グリッド空間における自律分散ロボット群の緩集合問題について", 研究報告アルゴリズム（AL）, 2017-AL-163(14), 1-8, (2017.05.).
4. 宮川歩，金鎔煥，片山喜章, "仮想グリッドネットワークにおける経路最適化分散アルゴリズムの改良", 電子情報通信学会技術研究報告 IEICE technical report : 信学技報 116(116), 49-56, (2016.06.).
5. 伊藤佳進, 片山喜章, 和田幸一, "共通座標系を有しないグリッド平面におけるファットロボットの集合," コンピュテーション研究会（IPSJ-AL連催） 講演論文集, pp.53-59, Jun.2014.
6. 宮永慎太郎，片山喜章，和田幸一，高橋直久，小林基成，森田正範: "WANET上でのクラスタ及び通信路構築自己安定アルゴリズムについて"， 情報処理学会 アルゴリズム研究会(AL111)，情処研報，Vol.2007， No.23， pp.9-16，(2007.03.09)，(鹿児島大学)．
7. 宮永慎太郎，片山喜章，和田幸一，高橋直久，小林基成，森田正範: "効率の良い統合・分離が可能な動的クラスタネットワーク構築アルゴリズムについて"， 電子情報通信学会 コンピュテーション研究会(COMP2005-58)，信学技法，Vol.105， No.679， pp.9-16，(2006.03.22)，(電気通信大学)．
8. 中村友貴，片山喜章，高橋直久: "木ネットワーク上でのトークン巡回故障封じ込め自己安定プロトコル"， 情報処理学会 アルゴリズム研究会 (2006-AL-104)，2005-AL-104(6)，pp.35--42, (2006.01.20)，(慶應義塾大学 矢上キャンパス)．
9. 中村友貴，片山喜章，高橋直久: "ノード及びリンク故障を考慮したエージェ ント巡回自己安定プロトコルについて"，信学技法(COMP2003-93)， Vol.103, No.723， pp.57-64，(2004.03.16)(名工大)．
10. 長谷川敏之，片山喜章，高橋直久: "経路情報を用いた生成木構成強安定プ ロトコルについて"，信学技法(COMP2003-92)，Vol.103, No.723， pp.49-56，(2004.03.16)(名工大)．

- 全国大会等

1. 鶴田直也, 金鎔煥, 片山喜章, "ペアロボットモデルによる物体被覆アルゴリズムについて", 2019年電子情報通信学会総合大会, (2019.03.).
2. 宮口直也, 金鎔煥, 片山喜章, "極小弱連結支配集合を求めるための故障封じ込め自己安定アルゴリズムについて", 2019年電子情報通信学会総合大会, (2019.03.).
3. 高橋一生, 金鎔煥, 片山喜章, "ペアロボットモデルにおける正三角形から直線への 形状形成アルゴリズムについて", 2019年電子情報通信学会総合大会, (2019.03.).
4. 澤田裕介, 金鎔煥, 片山喜章, "仮想グリッドネットワークにおける3点間の通信経路の自己最適化分散アルゴリズムについて", 2019年電子情報通信学会総合大会, (2019.03.).
5. 風岡弘樹，金鎔煥，片山喜章, "仮想グリッドネットワークにおける共通座標系を有しない経路最適化分散アルゴリズム", 2018年電子情報通信学会総合大会, (2018.03.).
6. 矢萩諒，金鎔煥，片山喜章, "効率的な状態空間探索のための反復MapReduce処理の可視化", 2018年電子情報通信学会総合大会, (2018.03.).
7. 山田涼斗，金鎔煥，片山喜章, "自律分散ロボットを用いたamoebot再現モデルに関する研究", 2018年電子情報通信学会総合大会, (2018.03.).
8. 青野宏紀，片山喜章，金鎔煥, "(2,2)-弱極大DAG構成自己安定アルゴリズムの研究", 2017年電子情報通信学会総合大会, (2017.03.).
9. 大藪匡記，金鎔煥，片山喜章, "二次元グリッド平面における自律分散ロボットによる一点包囲アルゴリズムの研究", 2017年電子情報通信学会総合大会, (2017.03.).
10. 長尾英剛，片山喜章，Yonghwan Kim，和田幸一, "三次元グリッド空間における自律分散ロボットの集合の研究", 2016年電子情報通信学会総合大会, (2016.03.).
11. Yonghwan Kim and Toshimitsu Masuzawa, "A Research on the Self-optimizing Distributed Algorithm Constructing Rectilinear Steiner Tree in Virtual Grid Networks", 情報処理学会第78回全国大会, (2016.03.).
12. 片山喜章，増澤利光，和田幸一: "木ネットワーク上での負荷分散自己安定 アルゴリズムについて"，2004年夏のL.A.シンポジウム，pp.11.1-11.6， (2004.07.15)(淡路島・夢舞台)．
13. 長谷川敏之，片山喜章，高橋直久: "生成木構成問題を解く強安定プロトコ ルに関する研究"，夏のL.A.シンポジウム(合歓の郷)，2003年夏のLAシンポ ジウム予稿集，pp. S7.1--S7.10，(2003.07.16)．

- ワークショップ

1. 高橋一生，金鎔煥，片山喜章， "自律移動ペアロボットモデルにおける正三角形から直線への形状形成アルゴリズムについて", 第15回情報科学ワークショップ, (2019.09.).
2. 澤田裕介，金鎔煥，片山喜章， "On a Self-Optimizing Three Nodes Routing Algorithm based on Local Information in Virtual Grid Networks", 第15回情報科学ワークショップ, (2019.09.).
3. 矢萩諒，金鎔煥，片山喜章，"A Parallel Branch-and-Bound Method using MapReduce and HBase", 第15回情報科学ワークショップ, (2019.09.).
4. 山田涼斗，金鎔煥，片山喜章，和田幸一, "ペアロボットモデルにおける直線⾏進と物体被覆アルゴリズムについて", 第14回情報科学ワークショップ, (2018.09.).
5. 大藪匡記，金鎔煥，片山喜章, "二次元グリッド平面における自律分散ロボットによる一点包囲アルゴリズムについて", 第13回情報科学ワークショップ, (2017.09.).
6. 青野宏紀，金鎔煥，片山喜章, "(2,2)-弱極大 DAG 構成自己安定アルゴリズムについて", 第13回情報科学ワークショップ, (2017.09.).
7. 金鎔煥，片山喜章, "3次元グリッドネットワーク上の自己最適化ルーティングアルゴリズム", 第12回情報科学ワークショップ, (2016.09.).
8. 伊藤佳進, 片山喜章, 和田幸一, "共通座標系を有しないグリッド平面におけるファットロボットの集合について," 第９回情報科学ワークショップ 講演論文集, 5-3, Sep.2013.
9. 岡本圭祐, 片山喜章, "メッセージサイズO(log n)の深さ優先探索木生成自己安定アルゴリズムについて," 第９回情報科学ワークショップ 講演論文集, 7-3, Sep.2013.
10. 佐々木敏晃，片山喜章，高橋直久: "背景と物体動作の連係方式を用いた動画生成システムの設計と実現"， 電子情報通信学会 第17回データ工学ワークショップ（DEWS2006），4B-i13，(2006.03.01-03)，（沖縄コンベンションセンター）．

- 修士論文・卒業論文

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

- 受賞等

1. 第14回情報科学ワークショップ プレゼンテーション賞, 山田涼斗, ペアロボットモデルにおける直線⾏進と物体被覆アルゴリズムについて, 2018.09.
2. 平成19年度情報処理学会東海支部 学生論文奨励賞，宮永慎太郎，動的アドホックネットワークでの効率の良い統合・分離が可能なクラスタネットワーク構築アルゴリズム

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