分散アルゴリズムの設計

分散アルゴリズムというのは，分散システムのためのアルゴリズムです．分散システムというのは，通信機能を持つ複数の計算主体が通信リンクで繋がれているシステムを言います．インターネットなどのネットワークもその一つの例です．計算主体は，パソコンなどの計算機であったり，スマートフォンなどのモバイルデバイスであったり，通信機能を持ったロボットである場合もあります．計算主体は，インターネットなどの大規模なネットワークを考えると，システム全体の状況を常に正確に把握しておくことは困難です．分散アルゴリズムは，自身に直接繋がれている計算主体の部分集合と自身の状態だけを基にしてどう動くか，を表すものです．つまり，各計算主体は，システムの局所的な情報を基に動きますが，結果としてシステム全体として上手く協調動作できるように分散アルゴリズムを設計しておく必要があるわけです．

分散システムでは，通信リンクが切断したり，メッセージが損失したり，計算主体のメモリ内容が外乱によって改変されたりといった一時故障が起こりやすいと言えます．そういった故障に対する耐性を持つ分散アルゴリズムの一つの枠組みに自己安定アルゴリズムがあります．自己安定アルゴリズムは，どのような一時故障が何度起きたとしても，それを引き金として，ネットワーク全体の状況を有限時間内に自動的に正常な状況に回復してくれる仕組みを持つ分散アルゴリズムです．

本グループでは，主に，ネットワークをグラフに，計算主体を節点に，通信リンクを辺に置き換えて，グラフの最適化問題にモデル化される問題を解く自己安定アルゴリズムを設計しています．