講演抄録/キーワード |
講演名 |
2007-03-05 11:15
モバイルエージェント間ゴシップの移動計算量について ○鈴木朋子(阪大)・泉 泰介(名工大)・大下福仁・角川裕次・増澤利光(阪大) |
抄録 |
(和) |
近年,分散システムの効果的な実現法として,モバイルエージェントを利用した設計法への期待が高まっている.モバイルエージェン
トシステムにおける最も基本的な機能の1 つとして全エージェント間での情報交換(ゴシップ) が挙げられる.ゴシップを実現する手法にエージェ
ント会合アルゴリズム(Rendezvous algorithm) がある.会合アルゴリズムは,同時刻にある1 つのノードに全てのエージェントを集合させるア
ルゴリズムである.しかし,ゴシップの実現に対し,同時刻にすべてのエージェントを集める必要はなく,複数エージェント間の情報伝播によりす
べてのエージェントが保持する情報を集めることが可能である.そこで本論文では,モバイルエージェントのゴシップ問題を新たに提案する.ゴ
シップ問題では,あるエージェントが他のエージェントの情報を得る方法として,1) そのエージェントに直接会う,2) そのエージェントに会った
ことのあるエージェントに会う,という2 つの方法がある.そのため,ゴシップアルゴリズムは会合アルゴリズムに比べ少ないエージェントの移
動回数で全エージェント間の情報交換を達成する.本論文では,様々なネットワークトポロジに対するゴシップアルゴリズムを提示し,それらの
アルゴリズムがエージェントの移動計算量の点で最適であることを示す. |
(英) |
Mobile-agent-based distributed systems are
attracting widespread attention as the adaptive and flexible systems:
mobile agents traverse the distributed system and carry out a task at
each node. In such mobile-agent-based systems, {\em gossip} is the most
fundamental scheme supporting cooperation among mobile agents.
It requires to accomplish all-to-all information exchange over all agents so
that each agent can obtain the all informations each agent initially has.
Rendezvous algorithms, which require that all the agents rendezvous on a node
at a time, can achieve this requirement, however it takes excessive cost
for our objective. In this paper, we newly introduce the mobile agent
gossip problem. In this problem, an agent can obtain the information of
another agent by meeting the agent itself or the agent that has already
got the information. The gossip scheme is expected to accomplish the
all-to-all information exchange with a smaller number of agents' moves
than the rendezvous algorithms. We propose mobile agent gossip algorithms on
several network topologies, and prove that all proposed algorithms
are asymptotically optimal in term of the number of moves. |
キーワード |
(和) |
モバイルエージェント / ゴシップ / 移動計算量 / 分散アルゴリズム / / / / |
(英) |
mobile agent / gossip / move complexity / distributed algorithm / / / / |
文献情報 |
信学技報, vol. 106, no. 566, COMP2006-54, pp. 29-36, 2007年3月. |
資料番号 |
COMP2006-54 |
発行日 |
2007-02-26 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 |
PDFダウンロード |
|