現代社会を支える情報システムの多くは、インターネット、IoT (Internet of Things)、センサネットワーク、そして複数のロボットが協調するシステムなど、多数の計算主体（プロセス、エージェント、ロボット）が通信を介して協調動作する分散システムです。本研究室では、このような分散システムにおいて、ユーザが安心して利用できるシステムを実現するための理論と技術を研究しています。特に、個々の要素が限られた局所情報のみに基づいて自律的に動作し、全体として高度な機能を実現する分散アルゴリズムの設計と解析を主軸としています。

分散アルゴリズムの研究のポイントは、計算資源や通信能力が限定された環境下において、高効率性と高信頼性を両立させることです。現実の大規模分散システムでは、全構成要素を集中管理することは不可能であり、各要素はバラバラなタイミングで動作します。さらに、通信の遅延、コンピュータの故障、さらには悪意のある攻撃（ビザンチン故障）が発生する可能性があります。このような不確実な環境下で、いかに少ない時間やコスト、メモリ量でタスクを完了させるか、そして、いかに過酷な故障に対して故障耐性を実現するかが、主要な研究課題です。

具体的な研究対象は多岐にわたります。まず、物理空間やネットワーク上を移動するモバイルロボット・エージェントに関しては、視界が制限されたロボットによる探索や、悪意あるエージェントが存在する環境での集合問題などを扱っています。ナノスケールの分子ロボットや低性能デバイスのネットワークを想定した個体群プロトコルでは、極小のメモリでリーダー選挙やグループ分割などを行う手法を研究しています。そして、システムがどのような異常状態に陥っても自律的に正常状態へ復帰する自己安定アルゴリズムの研究では、従来よりも高速かつ省メモリな手法や、新たな安定性の概念である緩安定（Loose-stabilization）の実現方法を研究しています。

多くの研究は、分散システムを抽象化した理論モデルを用いて、アルゴリズムの正当性と計算量（時間、空間、移動回数など）を理論的に証明することで裏付けています。理論的な限界（下界）を明らかにすると同時に、その限界に挑む最適または準最適なアルゴリズムを構築することで、分散システムの基盤となるさまざまな基礎理論を構築しています。

ネットワーク内を移動してデータ処理を行うモバイルエージェントの研究では、特にビザンチン故障 (Byzantine Faults) への対策に注力しています。ビザンチン故障とは、バグや乗っ取りによりエージェントが嘘の情報​​を流すなど、予測不能な振る舞いをする故障です。 本研究では、ノードに設置された認証機能付き白板 (Authenticated Whiteboard) を利用することで、一部のエージェントがビザンチン故障を起こしても、正常なエージェントを効率的に一点に集合させるアルゴリズムを提案しました。また、エージェントが訪問するだけで消滅してしまう危険なノード（ブラックホール）が存在する環境下において、ビザンチンエージェントの妨害に耐えつつブラックホールを特定する探索アルゴリズムも開発しています。また、部分集合（Partial Gathering）や均一配置（Uniform Deployment）といった問題に対しても、移動コストや時間を最適化するアルゴリズムを設計しています。

 個体群を等しいサイズの複数のグループに分ける一様分割（Uniform Partition）も重要なテーマです。これは、センサネットワークの負荷分散や分子ロボットの機能分化に応用可能です。 本研究では、個体群を2つのグループに分ける一様2分割や、より一般化した一様 k 分割を対象とし、それを実現するために必要な最小の状態数（空間計算量）を解明しました。すべての個体が通信可能な完全グラフだけでなく、任意の形状の通信グラフに対しても研究を進めています。

 従来の自己安定は「一度正しい状態になったら、故障がない限り永遠にその状態を保つ」ということを要求します。しかし、個体群プロトコルのようなリソース制約の厳しい環境では、この厳密な条件を満たすことが不可能な場合があります（例：個体数が未知の場合のリーダー選挙など）。 そこで本研究では、緩安定（Loose-stabilization）という新しい概念を導入しました。これは、収束後の状態維持を「永遠」ではなく「実用上十分に長い時間（例：個体数の指数関数的な時間）保証することで、厳密な自己安定が不可能な問題に対しても解決策を与えるものです。この概念を用いることで、個体群プロトコルモデルにおいて、個体数を正確に知らなくても確率的にリーダーを選出し、長時間維持するアルゴリズムを実現しました。