無線接続された移動計算機を含むネットワーク上の分散アルゴリズム

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

無線接続された移動計算機を含むネットワーク上の分散アルゴリズムについて研究を行い、以下の結果を得た。1.無線接続された移動計算機を含むネットワークの理論的モデルの提案、及び、基本的な分散アルゴリズムの設計と解析:無線接続された移動計算機を含むネットワークの大きな特徴は、移動計算機の移動により、その接続関係が動的に変化することである。この移動計算機の接続関係の変化を反映した分散アルゴリズム設計のためのネットワークモデルを提案した。さらに、このモデル上で、基本的かつ重要な問題であるスナップショット問題を定義し、スナップショット問題を解く分散アルゴリズムの設計と解析を行った。2.ネットワーク形状変化に対応して、解を効率良く再計算する分散アルゴリズムの設計と解析:移動計算機の移動により、ネットワークの形状が変化した場合、形状変化に応じて、問題の解を再計算する必要がある。本研究では、ネットワークの2連結成分を求める問題を対象とし、ネットワーク形状が変化したときに、その解を更新する分散アルゴリズムを設計し、その計算量の解析を行った。3.形状が変化するネットワークでの故障耐性のある分散アルゴリズムの設計と解析:計算機の移動によるネットワーク形状の変化と、計算機の故障の両方に対応できる分散アルゴリズムの可能性について考察した。具体例として、トポロジ問題とリーダ選択問題を取り上げ、これらの問題に対し、動的ネットワークで故障耐性のある分散アルゴリズムを設計した。