モバイルエージェント間ゴシップの移動計算量について
スポンサーリンク
概要
- 論文の詳細を見る
近年,分散システムの効果的な実現法として,モバイルエージェントを利用した設計法への期待が高まっている.モバイルエージェントシステムにおける最も基本的な機能の1つとして全エージェント間での情報交換(ゴシップ)が挙げられる.ゴシップを実現する手法にエージェント会合アルゴリズム(Rendezvous algorithm)がある.会合アルゴリズムは,同時刻にある1つのノードに全てのエージェントを集合させるアルゴリズムである.しかし,ゴシップの実現に対し,同時刻にすべてのエージェントを集める必要はなく,複数エージェント間の情報伝播によりすべてのエージェントが保持する情報を集めることが可能である.そこで本論文では,モバイルエージェントのゴシップ問題を新たに提案する.ゴシップ問題では,あるエージェントが他のエージェントの情報を得る方法として,1)そのエージェントに直接会う,2)そのエージェントに会ったことのあるエージェントに会う,という2つの方法がある.そのため,ゴシップアルゴリズムは会合アルゴリズムに比べ少ないエージェントの移動回数で全エージェント間の情報交換を達成する.本論文では,様々なネットワークトポロジに対するゴシップアルゴリズムを提示し,それらのアルゴリズムがエージェントの移動計算量の点で最適であることを示す.
- 2007-02-26
著者
-
角川 裕次
大阪大学大学院情報科学研究科
-
泉 泰介
名古屋工業大学大学院工学研究科
-
増澤 利光
大阪大学大学院情報科学研究科
-
大下 福仁
大阪大学大学院情報科学研究科
-
鈴木 朋子
大阪大学大学院情報科学研究科
-
大下 福仁
大阪大学大学院基礎工学研究科情報数理系
-
泉 泰介
名古屋工業大学
-
角川 裕次
阪大
関連論文
- キャッシュを行うP2Pシステムにおける時間を基にした評価手法(コンカレントシステム, 一般)
- 証明書分散問題の近似可能性について
- 大阪大学情報科学研究科におけるソフトウェアデザイン工学高度人材育成への取り組み
- 木ネットワークにおけるビザンチン故障耐性を有する自己安定辺彩色プロトコル
- Population protocolにおけるオラクルをもたない自己安定リーダー選挙問題の可解性に関して
- A Dynamic Reconfiguration Tolerant Self-stabilizing Token Circulation Algorithm in Ad-Hoc Networks (Evolutionary Advancement in Fundamental Theories of Computer Science)
- アドホックネットワーク向けトークン巡回自己安定分散アルゴリズム
- A Universal Self-Stabilizing Mutual Exclusion Algorithm (New Developments of Theory of Computation and Algorithms)
- テスト駆動開発に基づくプログラミング学習支援システム : 初心者開発者のためのセルフトレーニングアーキテクチャ
- 通信遅延が大きな並列計算環境に対するタスクスケジュールのためのクラスタリングアルゴリズム(アルゴリズム・数値計算)
- 通信遅延を考慮したタスクスケジューリングアルゴリズム(アルゴリズム一般)
- 通信遅延を考慮したタスクスケジューリングアルゴリズム
- スタイナー木問題を解く自己安定分散アルゴリズム
- P2Pシステムにおけるブルームフィルタを利用したオーバレイネットワークの構築(セッションB-1:P2P・オーバーレイネットワーク(1))
- P2Pネットワークにおける決定性減衰型ブルームフィルタの提案と検索効率の評価(インターネットの品質評価・品質管理技術,ネットワーク品質,トラヒック計測,一般)
- P2Pネットワークにおけるブルームフィルタを利用したインデックス情報散布法の改良(次世代ネットワーク,SIP・プレゼンス,一般)
- 極大局所リーダー選挙問題を解く分散アルゴリズム
- B-7-80 新世代ネットワークサービス基盤としての仮想化技術のモデル化に関する一考察(B-7. 情報ネットワーク,一般セッション)
- 無線モバイルユーザのための最適「寄り道」経路の特性(一般,移動通信ワークショップ)
- 構造化オーバレイネットワークにおける故障耐性向上のための経路多重化法(ディペンダブルコンピューティング)
- 分散ハッシュテーブルChordにおける故障耐性向上のための経路の多重化手法(フォトニックネットワークシステム,光ルーチング,ブロードバンドアプリケーション,一般)
- 白板を利用したモバイルエージェントによる効率的なグラフ探索
- 無線LAN環境におけるアトラクター選択を用いた経路選択手法
- モバイルアドホックネットワークにおけるGPSを用いたACOルーティング
- 無線LAN環境におけるアトラクター選択を用いた経路選択手法
- モバイルアドホックネットワークにおけるGPSを用いたACOルーティング
- 類似実行に基づく耐故障分散アルゴリズム理解支援システムの提案(Session 2)
- 領域被覆のためのセンサネットワークアルゴリズム(セッション9-A : アドホックネットワーク・センサネットワーク(4))
- 領域被覆のためのセンサネットワークアルゴリズム(セッション9-A : アドホックネットワーク・センサネットワーク(4))
- モバイルエージェント間ゴシップの移動計算量について
- 動的ネットワークにおける生態系パラダイムに基づく静的資源数制御
- 動的ネットワークにおける生態系パラダイムに基づくモバイルエージェント数制御(エージェント・学習)
- トポロジ変化に対して出力の変化数を最小化する全域木構成分散アルゴリズム
- モバイルアドホックネットワークにおける公平性の高い自己安定相互排除プロトコル(研究速報)
- トポロジ変化の影響を抑えたモバイルアドホックネットワーク向け自己安定相互排除プロトコル(セッション4-A : アドホックネットワーク・センサネットワーク(2))
- トポロジ変化の影響を抑えたモバイルアドホックネットワーク向け自己安定相互排除プロトコル(セッション4-A : アドホックネットワーク・センサネットワーク(2))
- Emulation of ring protocols on trees preserving fault-containment (コンピュテーション)
- 無線ネットワークにおける距離2の彩色を利用したTDMAスケジュール手法(無線・モバイルネットワーク)
- 無線ネットワークにおける距離2の彩色を利用したTDMAスケジュール手法(セッション5: 無線ネットワーク)
- 体験的な分散アルゴリズム協調学習を支援するシステムの提案
- 観測に一様な誤差を生じるモデルでの自律分散ロボット群の一点収束について
- 偶数台の自律分散ロボット群に対するリング上での一点集合問題について
- 4台の自律分散ロボット群による正方形形成について
- 動的コンパスを持つロボット群の一点集合問題に対する許容変化量最適なアルゴリズム
- 故障したコンパスを持つ二台の自律分散ロボットに対する一点集合問題の可解性について
- ET2009-86 アルゴリズム学習向け誤り発見型演習のためのカスタマイズ可能な問題自動生成システム(学習データの蓄積・分析・共有/一般)
- 複数グループのオンライン議論を同時にサポートする自動助言システムの構築(セッション議論支援)
- アルゴリズム学習における間違い探し形式の演習課題を自動生成する手法の提案と評価
- アドホックネットワークの経路構築における非協調行動の抑制手法について(アドホックネットワーク,無線ネットワーク,有線/無線シームレスネットワーク,ネットワーク制御,無線通信一般)
- モバイルP2Pにおけるレーン構造を用いた資源探索手法(セッションB-8:P2P・オーバーレイネットワーク(2))
- P2Pシステムにおける動的ランダムオーバーレイの構築手法(セッションB-1:P2P・オーバーレイネットワーク(1))
- モバイルP2Pにおけるレーン構造を用いた資源探索手法(セッションB-8:P2P・オーバーレイネットワーク(2))
- P2Pシステムにおける動的ランダムオーバーレイの構築手法(セッションB-1:P2P・オーバーレイネットワーク(1))
- P2Pシステムにおけるブルームフィルタを利用したオーバレイネットワークの構築(セッションB-1:P2P・オーバーレイネットワーク(1))
- 議論活動における調査資料の活用を支援するシステムHAKASEの構築
- 極大クリーク分割に基づく自己安定クラスタリングアルゴリズム
- メッセージの確率的な消失を考慮した耐故障合意アルゴリズム
- アルゴリズム学習における誤りからの学習を実現する演習課題の自動生成手法(オープンソースソフトウェアの教育利用/一般)
- 動的環境に於けるコータリ構成アルゴリズム(コンカレントシステム, 一般)
- A-012 分散グループ相互排除アルゴリズム(A.モデル・アルゴリズム・プログラミング)
- Timed Uniform Consensus Protocol Tolerating Crash and Timing Faults
- Timed Uniform Consensus Protocol Tolerating Crash and Timing Faults
- タイミング故障および停止故障に対する故障耐性を有するアトミックブロードキャスト
- 相互無関係並列マシンにおける一般化多組織スケジューリング
- MSTに基づくSVMパス追跡を用いた多重多変量2標本検定による遺伝子群解析に関する一考察(IBIS2010(情報論的学習理論ワークショップ))
- A-015 アドホックネットワーク向け自己安定トークン巡回アルゴリズムの実験的評価(A.モデル・アルゴリズム・プログラミング)
- 分散データ構造スキップグラフの探索頻度偏りを考慮した拡張について(セッション3)
- 確率的コーラムシステムに基づく負荷分散アルゴリズムとその実験的評価
- 確率的コーラムシステムを用いた資源割り当てアルゴリズム
- 2-327 ラフ集合を用いたWeb学習ナビゲータの作成((10)e-ラーニングシステム)
- Web上の学習ナビゲータの作成法について(e-Learning教育システムの成果と目指すべきもの/一般)
- Model Checkingを用いた並行プログラミング学習支援システムの試作
- A-013 局所名前付け自己安定アルゴリズム(A.モデル・アルゴリズム・プログラミング)
- K-019 モデルチェッキングを用いたアセンブリ並行プログラミング学習支援システム(K.ヒューマンコミュニケーション&インタラクション)
- P2Pシステムにおける確率的弱コーラムシステムを用いた自己適応的探索手法(セッション4)
- A Weakly-Adaptive Condition-Based Consensus Algorithm in Asynchronous Distributed Systems
- 1ステップ分散合意問題の可解性について(ディペンダブルソフトウェアとネットワーク及び一般)
- 分散環境における順位つき資源への部分探索法の提案(セッション5-A : 分散システム)
- 分散環境における順位つき資源への部分探索法の提案(セッション5-A : 分散システム)
- 分散環境における順位つき資源への部分探索法の提案
- 1ステップ分散合意問題の可能性について
- Synchronous Condition-Based Consensus Algorithm Adapting to Input-Vector Legality
- プロセスの出現・消滅に対応したコーザルブロードキャスト
- A-016 確率的弱コーラムシステムを用いたP2Pオブジェクト検索アルゴリズムの実験的評価(A.モデル・アルゴリズム・プログラミング)
- 確率的弱コーラムシステムを用いたP2P環境オブジェクト検索アルゴリズム
- プログラムの正しさの理解を目的とした教材作成システム
- センサネットワークにおけるエネルギー消費の少ないトラッキングアルゴリズム
- アルゴリズム学習向け誤り発見型演習のためのカスタマイズ可能な問題自動生成システム
- 複数のフォントフォーマットを透過的に利用できるフォントモジュールVFlib
- プロセスマイグレーションを用いたデータグリッド環境における並列計算システム(コンカレントシステム, 一般)
- オーエンス・ルイス : アンビエント環境制御を用いた知的オフィスチェアの提案(アンビエントインテリジェンス技術とその応用)
- 自己安定分散システムの検証システム
- Randomized Rendezvous of Multiple Mobile Agents in Anonymous Unidirectional Ring Networks (コンピュテーション)
- 同期リングにおけるモバイルエージェント均一配置アルゴリズム (コンピュテーション)
- マルチコアCPU環境における仮想計算機を用いたHadoopシステムの評価
- 匿名単方向リングネットワークにおけるモバイルエージェント集合問題に対する乱択アルゴリズム
- MapReduce計算の並列複雑度について
- 同期リングにおけるモバイルエージェント均一配置アルゴリズム
- 自己安定分散アルゴリズムの自動検証システム
- 同期リングにおけるモバイルエージェント均一配置アルゴリズム