研究内容の紹介

目次

• 分散アルゴリズム理論
• センサーネットワークシステムソフトウエア
• 教育工学
• 番外編 (VFlib プロジェクト/TeX-Guy プロジェクト)
• 論文リスト

キーワード: 分散アルゴリズム, 分散計算論, センサーネットワーク, 自己安定システム, コーラム(quorum)システム, Peer-to-Peer (P2P), モデル検証, 計算機プログラミング教育, 教育工学,

分散アルゴリズム理論

分散アルゴリズム理論 (Distributed Algorithm Theory) の研究を行なうテーマです。
ネットワークで結ばれた計算機が協調してある問題を解くには、 どのようにすればより効率よく解けるのか、 最低限どのくらいの計算の手間がかかるのか、 そもそもその問題は解くことができるのか、 といったことを理論的に明らかにして行く研究です。

分散アルゴリズムとは

• 講義資料: 分散アルゴリズム入門 [PDF] (ちょっと小難しい入門)

研究成果(その1)
自己安定システムの研究:

• Hirotsugu Kakugawa and Sayaka Kamei,
  "A self-stabilizing distributed algorithm for the bounded lattice domination problems under the distance-2 model,"
  Special Issue on Parallel and Distributed Computing and Networking (CANDAR 2022),
  Concurrency and Computation: Practice and Experience (CPE),
  Article ID: CPE7902 (accepted; to appear)
  
• Hirotsugu Kakugawa and Toshimitsu Masuzawa,
  "Convergence Time Analysis of Self-Stabilizing Algorithms in Wireless Sensor Networks with Unreliable Links",
  10th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS2008), Detroit, USA, Nov 21-23, 2008.
• Sayaka Kamei and Hirotsugu Kakugawa,
  "A Self-Stabilizing Distributed Algorithm for the Steiner Tree Problem",
  IEICE Transactions on Information and Systems, Vol. E87-D, No. 2, pp.299-307, Feb. 2004.
• 角川裕次, 山下雅史, "Uniform and Self-Stabilizing Fair Mutual Exclusion on Unidirectional Rings under Unfair Distributed Daemon", Journal of Parallel and Distributed Computing, Vol. 62, No. 5, pp. 885--898, May 2002.
• 石井博子, 角川裕次, "A Self-Stabilizing Algorithm for Finding Cliques in Distributed Systems," International Workshop on Self-Repairing and Self-Configurable Distributed Systems (RCDS2002), Osaka, Japan, October 13, 2002, in Proceedings of the 21st Symposium on Reliable Distributed Systems (SRDS2002), pp. 390--395
• 亀井清華, 角川裕次, "A Self-Stabilizing Algorithm for the Steiner Tree Problem,"
  International Workshop on Self-Repairing and Self-Configurable Distributed Systems (RCDS2002), Osaka, Japan, October 13, 2002, in Proceedings of the 21st Symposium on Reliable Distributed Systems (SRDS2002), pp. 396--401.
• 最新の論文リスト

研究成果(その2):
コーラムシステムの研究:

• Hirotsugu Kakugawa, Sayama Kamei and Toshimitsu Masuzawa
  "A Token-Based Distributed Group Mutual Exclusion Algorithm with Quorums",
  IEEE Transactions on Parallel & Distributed Systems, Vol. 19, No. 9, pp. 1153 - 1166, September, 2008.
• Mie Toyomura, Sayaka Kamei and Hirotsugu Kakugawa,
  "A Quorum-Based Distributed Algorithm for Group Mutual Exclusion,"
  Proceedings of the Fourth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT),
  pp. 742-746, Chengdu, Sichuan, China (中国四川省成都), Aug. 27-29, 2003.
  [IEEE Press, ISBN 0-7803-7840-7]
• 吉村 英明, 三浦健, 角川裕次, "A Distributed Algorithm for Resource Allocation with Probabilistic Quorum Systems," Proceedings of the International Conference on Networks, Parallel and Distributed Processing, and Applications (NPDPA 2002), pp. 241--246, Tsukuba, Japan, October 1--4, 2002.
• 最新の論文リスト

研究成果(その3):
Peer-to-Peer ファイル共有システムの研究 (コーラムを使いしかも自己安定):

• Ken Miura, Taro Tagawa and Hirotsugu Kakugawa,
  "A Quorum-Based Protocol for Searching Objects in Peer-to-peer Networks",
  IEEE Transactions on Parallel & Distributed Systems, Vol. 17, No. 1, pp. 25-37, January, 2006.
• 三浦健, 角川裕次, "確率的弱コーラムシステムを用いたP2P環境オブジェクト検索アルゴリズム", 情報処理学会 アルゴリズム研究会＠中央大学, 2004-AL-93, pp. 49-56, 2004年1月.　
• 最新の論文リスト

センサーネットワークシステムソフトウエア

センサーと IEEE 802.15.4 無線通信デバイスをマイコンに 接続した超小型CPUボードを多数配置し、 様々な環境測定や異常監視をおこなうシステムに関する研究です。 多数のノードを無造作に配置し、 電池ぎれのノードが出てきても正しく動作させるには、 自己安定、自己修復、自己組織化といった Self-* 性をシステムソフトウエアに持たせることが必須となります。

本研究テーマでは、長年にわたる 分散アルゴリズム理論および自己安定分散システム研究の成果を 実システムに応用すべく、システム開発を進めています。

研究成果

• Hirotsugu Kakugawa, Yukiko Yamauchi, Sayaka Kamei and Toshimitsu Masuzawa, "Closure and Convergence of Non-Silent Self-Stabilizing Algorithms by Cached Sensornet Transformation with Unreliable Links", 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 428-442, November 2009.
• Hirotsugu Kakugawa and Toshimitsu Masuzawa, "Convergence Time Analysis of Self-Stabilizing Algorithms in Wireless Sensor Networks with Unreliable Links", 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 173-187, Detroit, USA, Nov 21-23, 2008.
• Kazuyuki Yoshida, Hirotsugu Kakugawa, and Toshimitsu Masuzawa, "Observation on Lightweight Implementation of Self-Stabilizing Node Clustering Algorithms in Sensor Networks," IASTED International Conference on Sensor Networks, Crete, Greece, September 29 - October 2, 2008.

教育工学

計算機科学のオンライン学習用ソフトウエア (Computer Assisted Learning System) の研究、とくにプログラミングを中心とする教育のための 学習支援ソフトウエアの開発研究しています。

研究成果(その1)
アルゴリズムの学習を、誤りの発見に基づいて学ぶシステムの提案。 正しいソースコードに対して自動的に教育上有用な誤りを自動挿入をおこなう。

• 長瀧寛之, 伊藤亮太, 大下福仁, 角川裕次, 増澤利光, "アルゴリズム学習における間違い探し形式の演習課題を 自動生成する手法の提案と評価", 情報処理学会論文誌, Vol.49, No.10, pp.3366-3376, Oct. 2008.
• 最新の論文リスト

研究成果(その2)
正しい並行プログラムを書くために、 誤りを検知し、それを提示することで、学習を支援するシステム。 誤りの検知は、モデル検証系 (model checking system) を用いて行なう。 また、逐次的アルゴリズムでは、 ホア論理を利用してプログラムの正しさを論理的に理解し、 最終的には、ループ不変量などを考えて、 自力で正しいプログラムを書けるように 学習を支援するシステムを構築しています。

• Eisuke Yoshida and Hirotsugu Kakugawa,
  "A Learning System for the Problem of Mutual Exclusion in Multithreaded Programming,"
  IEEE International Conference on Advanced Learning Technologies (ICALT), Joensuu, Finland, Aug. 2004.
  
• 鶴見誠悟, 角川裕次, "Model Checking を用いた並行プログラミング学習支援システムの試作", 情報処理学会 コンピュータと教育研究会, 2002年12月.
• 森正, 角川裕次, 阿江忠, "プログラムの正しさの理解を目的とした教材作成システム", 情報処理学会 コンピューターと教育研究会, 2001年 10月13日.
• H. Kakugawa and T. Mori, "Toward an Algorithm Education System on the Web," 13th International Conference on Systems Research, Informatics and Cybernetics (InterSymp-2001), Barden-Barden, Germany, Aug. 2001.
• 最新の論文リスト

VFlib / TeX-Guy プロジェクト

様々なフォーマットのフォントを 統一的な API で利用可能とするフォントラスタライザのライブラリ、 ならびに、 組版システム TeX 用 DVI ファイルのプリンタドライバ/プレビューア パッケージ TeX-Guy を開発しています。

学術的な内容よりも、 優れたソフトウエアの開発が最優先のプロジェクトです。 成果ソフトウエアは全てオープンソースのフリーソフトウエアとして 無料で公開しています。

VFlib

フォントファイルといっても、 TrueType, Type1, PCF, BDF, PK など、様々なデータ形式のものが存在します。 それぞれに独自の特徴を持ち、互いに互換性がありません。 様々なデータ形式のフォントを混在して利用可能とする ソフトウエアを作成するのは容易ではありません。 というのも、オペーレーティングシステムやウインドウシステムで サポートされていないデータ形式のフォントを利用可能とするには、 アプリケーションソフトウエアごとにフォントファイルを読み出す ルーチンをプログラマが自分で書かないといけないからです。
VFlib はさまざまなデータ形式のフォントを 混在して利用できるようにした、C 言語でのライブラリです。 どのようなデータ形式フォントであっても フォントの利用方法は同じとなるように、 C 言語の関数呼び出し形式 (API) を設計しているため、 フォントファイルのデータ形式を全く意識せずに、 フォントを利用可能にしています。 また、オペーレーティングシステムやウインドウシステムが 提供するフォント機能は一切使用しない設計と実装にしているため、 様々な動作環境(オペーレティングシステム/ウインドウシステム)で 動作可能としています。

• まずはこれを読もう: VFlib ってなあに? VFlib の概要 (日本語)
• VFlib の Web ページ
• Hirotsugu Kakugawa, "Unified Access to Various Fonts: VFlib Approach", (招待講演) m17n2000: Fourth International Symposium on Multilingual Information Processing,, Tsukuba JAPAN, March 25--27, 2000. [発表スライド]
• H. Kakugawa, M. Nishikimi, N. Takahashi, S. Tomura, and K. Handa, "A General Purpose Font Module for Multilingual Application Programs", Software - Practice and Experience, Volume 31 Issue 15, pp. 1487--1508, December 2001.

TeX-Guy

TeX の DVI ファイルは組版結果のファイルであって文字の画像は含まれていません。 そのため、プリンタに印字するには、 フォント名、文字コード、位置情報から文字の画像をフォントファイルから取出し、 文字画像を必要な大きさに拡大/縮小し、 プリンタの制御コードに合わせて文字画像をプリンタに送信、 ページの印字を行なわないと行けません。
プリンタごとに制御コード体系が異るし、画面にも表示できれば便利なのですが、 ソフトウエア一つ一つで上記の動作を行なうプログラムを個別作成するのは 大変です。 そこで、出力機器(プリンタ/ウインドウ/画像ファイルなど) を制御するプログラムコードを追加するだけで TeX 文書の表示や印刷ができるようにするものが TeX-Guy パッケージの中心である DVIlib です。
DVIlib は機器非依存の DVI ファイル解釈システムで、 C 言語プログラムのライブラリとして設計／実装しています。 TeX-Guy パッケージには DVIlib のほか、 X Window System 上でのプレビューアを数種類、 いくつかのプリンタドライバや画像ファイル変換ソフトウエアが含まれています。

• TeX-Guy プロジェクトの Web ページ
• TeX 文書表示/印刷アプリケーションソフトウエアの構造図
• プレビューアー xgdvi の画面例
• 論文: Hirotsugu Kakugawa, "A Device Independent DVI Interpreter Library for Various Output Devices", TUG 2000 Conferece, pp. 101-107, Wadham College, Oxford, UK, Aug. 2000.