発表者が学生時代から十数年来取り組んでいる分散計算理論がどのような分野であるのか，最近の研究事例2つを通してご紹介いたします．具体的には，
 (i) 個体群モデルにおけるリーダ選挙問題，および，
 (ii) モバイルエージェントによるビザンチン集合問題
について，問題設定やこれまでに発見されたいくつかのアルゴリズムをご解説いたします．

 

個体群モデルとは，消極移動（自分で制御できない移動）を絶えず行う微小で計算資源に乏しい計算機で構成するネットワークを表現する分散計算のモデルです．このモデルは2004年にAngluinらによって提案されて以来，盛んに研究が行われてきました．とりわけ，リーダ選挙問題と多数決問題のふたつは大変良く研究されている問題で，前者については，2020年にBerenbrinkらによってついに時間最適かつ空間最適なアルゴリズムが発見されました．本講演では，このリーダ選挙問題について解説します．

 

モバイルエージェントとは，計算機ネットワーク上を自律的に移動するソフトウェアのことです．ネットワーク上に存在するすべてのエージェントをひとつの計算機に集める集合問題は基本的かつ重要な問題で，分散計算理論のコミュニティでは大変よく研究されています．本講演では，ネットワーク上の一部のエージェントが任意の敵対的な行動を取る場合にも正常なエージェントをひとつの計算機に集合させることを目的としたビザンチン集合問題を紹介します．