ネットワーク進化と分散アルゴリズム-テラ時代の分散アルゴリズム工学

本申請で、申請目的を説明するために、分散システムのエージェント数は既にギガで測られる時代にあり、テラの時代が近づきつつある、世界人口6.13x10^9の約半数がインターネットに組織されている。申請時点でGoogleは4.29x10^9個のホームページを検索可能であると書いた。もちろん実測されていないが、ホームページ数は既に200億(2x10^<10>)を越えて留まる所を知らない。このように、急速に変化するネットワークが本研究の対象である。この数年、申請者は巨大なネットワークの制御を統計力学の立場から研究を進めて来た。粒子の制御と計算機ネットワークの制御の大きな相違の一つは、粒子には名前が無いのに対して、従来の計算機ネットワークの制御には識別子の存在が基本的であった。すなわち、対象としたのは匿名の大域的情報を持たないモーバイルネットワーク(匿名自律分散ロボットシステムと、しても見做し得る)である。この視点から本年度は大きく2点の研究に取り組んだ。一つは匿名自律分散ロボットの合意問題、もう一つは高速な乱歩の設計である。匿名自律分散ロボットの合意に関しては、座標系のばらつきが合意に及ぼす影響について議論した。乱歩設計については、対象とするグラフトポロジー情報を最大限に利用することにより、ある特徴を持つグラフにおいては非常に高速な乱歩が設計できることを示した。

本申請で、申請目的を説明するために、分散システムのエージェント数は既にギガで測られる時代にあり、テラの時代が近づきつつある、世界人口6.13x10^9の約半数がインターネットに組織されている。申請時点でGoogleは4.29x10^9個のホームページを検索可能であると書いた。もちろん実測されていないが、ホームページ数は既に200億(2x10^<10>)を越えて留まる所を知らない。このように、急速に変化するネットワークが本研究の対象である。この数年、申請者は巨大なネットワークの制御を統計力学の立場から研究を進めて来た。粒子の制御と計算機ネットワークの制御の大きな相違の一つは、粒子には名前が無いのに対して、従来の計算機ネットワークの制御には識別子の存在が基本的であった。すなわち、対象としたのは匿名の大域的情報を持たないモーバイルネットワーク(匿名自律分散ロボットシステムと、しても見做し得る)である。この視点から本年度は大きく2点の研究に取り組んだ。一つは匿名自律分散ロボットの合意問題、もう一つは高速な乱歩の設計である。匿名自律分散ロボットの合意に関しては、座標系のばらつきが合意に及ぼす影響について議論した。乱歩設計については、対象とするグラフトポロジー情報を最大限に利用することにより、ある特徴を持つグラフにおいては非常に高速な乱歩が設計できることを示した。