動的ネットワークにおける動的タスクのための適応的な耐故障性を持つ分散アルゴリズム

点击翻译按钮获取中文摘要

本研究の目的としては，動的タスクのための自己安定アルゴリズムを安全に収束させることを掲げ，そのようなタスクの一つとして局所的危険区域問題を扱ってきたが，この問題では，各状況で危険区域内に入る計算機集合が極小支配集合を形成しているなどの特徴が見られることが分かってきた．そこで，最終年度は，マイナス支配集合問題やその拡張であるマイナス（L,K,Z)支配集合問題，さらに２－極小支配集合問題に対する自己安定アルゴリズムの設計を行い，それらの正しさを証明した．今後，これらの問題を動的タスクに拡張し，新たな自己安定アルゴリズムの設計および安全収束化を目指す計画である．また，既存の状態通信モデルを仮定したトークン巡回自己安定アルゴリズムにおいて，これをメッセージパッシングモデルに変換すると，トークンが消失する瞬間があることが分かっていたので，メッセージパッシングモデルに変換しても常に1つのトークンが存在するような自己安定アルゴリズムの設計を行った．さらに，動的タスクや動的ネットワークを考えるために，低機能なモバイルロボットモデルを対象とした研究も進めており，本研究最終年度では，ビザンチン故障を起こしたモバイルロボットが存在する中での自己安定アルゴリズムの設計と，モバイルロボットをグリッドネットワーク上の最大独立点集合を形成する位置に配置する分散アルゴリズムの設計を行った．