文献

J-GLOBAL ID：201802225503237185   整理番号：18A1039266

非同期リングにおけるモバイルエージェントの一様展開【JST・京大機械翻訳】

Uniform deployment of mobile agents in asynchronous rings

著者 (5件)： Shibata Masahiro (Kyushu Institute of Technology, 680-4, Kawadu, Iizuka, Fukuoka, 820-8502, Japan) ,  Mega Toshiya (Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan) ,  Ooshita Fukuhito (Graduate School of Information Science, NAIST, Takayama 8916-5, Ikoma, Nara 630-0192, Japan) ,  Kakugawa Hirotsugu (Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan) ,  Masuzawa Toshimitsu (Graduate School of Information Science and Technology, Osaka University, 1-5 Yamadaoka, Suita, Osaka 565-0871, Japan)
資料名： Journal of Parallel and Distributed Computing  (Journal of Parallel and Distributed Computing)
巻： 119  ページ： 92-106  発行年： 2018年 
JST資料番号： D0613B  ISSN： 0743-7315  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,リングに均一に広がるエージェントを必要とする非同期一方向リングにおける移動エージェントの均一配置問題を考察した。均一配置問題は,同じノードに適合するエージェントを必要とするランデブー問題と著しく対照的である。ランデブーは対称性を破ることを目的としているが,均一配置は対称性を達成することを目的としている。対称性の破れは分散系において困難であり,ランデブー問題はいくつかの初期配置から解くことができないことはよく知られている。そこで,著者らは,一様な配置問題が解決可能性に及ぼす影響を明らかにすることに興味を持ち,エージェントの数はランデブー問題と比較して移動する。k(またはn)の知識を持つ2つの問題設定を考慮し,kがエージェントの数であり,nがノードの数であるkまたはnの知識を持たない。まず,kの知識を持つエージェント(kとnが与えられた場合に容易に得られる)を考察した。この場合,2つのアルゴリズムを提案した。最初のアルゴリズムは,停止検出によって一様な配置問題を解決した。このアルゴリズムは,エージェント当たりO(klogn)メモリ空間,O(n)時間,およびO(kn)全移動を必要とする。第2のアルゴリズムはまた,終端検出によって一様な配置問題を解決した。このアルゴリズムは,エージェント当たりのメモリ空間をO(logn)に減少させるが,O(nlogk)時間を使用し,O(kn)の全移動を必要とする。両方のアルゴリズムは,エージェントが問題を解決するためにΩ(kn)全体の動きを必要とするようないくつかの初期構成があるので,全移動に関して漸近的に最適である。次に,kまたはnの知識のないエージェントを考察した。この場合,終端検出が必要な場合には,均一配置問題を解くアルゴリズムは存在しないことを示した。この理由のために,終端検出を必要としない緩和均一配置問題を考察し,緩和均一配置問題を解くアルゴリズムを提案した。このアルゴリズムは,初期構成が対称度lを持つとき,エージェント当たりO((k/l)log(n/l))メモリ空間,O(n/l)時間,およびO(kn/l)全移動を必要とする。これは,初期構成がより高い対称度(すなわち,均一配置に近い)を持つとき,アルゴリズムがより効率的に問題を解決できることを意味する。すべての提案したアルゴリズムが任意の初期構成から一様な配置を達成することに注目し,ランデブー問題がいくつかの初期構成から解けないので,ランデブー問題とは著しく異なる。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  対称性 ,  トークン ,  対称性の破れ ,  分散系 ,  記憶装置 ,  緩和現象 ,  配置問題 ,  *エージェント
準シソーラス用語： 分散システム ,  リングネットワーク , 【Automatic Indexing@JST】

著者キーワード (6件)： 分散システム ,  モバイルエージェント ,  均一展開 ,  リングネットワーク ,  トークン ,  対称度

分類 (1件)： ディジタル計算機方式一般  (JC02010O)

タイトルに関連する用語 (3件)： 非同期 ,  モバイルエージェント ,  展開