| 講演名 | 2012-05-14 非同期リングにおけるモバイルエージェント部分集合アルゴリズム 柴田 将拡, 川合 慎治, 大下 福仁, 角川 裕次, 増澤 利光, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 本稿では,非同期リングネットワークにおけるモバイルエージェントの部分集合問題について考察する.部分集合問題とは,集合すべきエージェント数gが与えられたとき,すべてのエージェントがサイズ(エージェント数)g以上のグループに分かれて集合する問題である.本稿では,アルゴリズムが決定性で,エージェントにIDがある場合と,アルゴリズムが乱択で,エージェントにIDがない場合に,部分集合問題を解決するアルゴリズムを提案する.そして,決定性アルゴリズムでは,ノード数をnとしたときに,総移動回数の上界がO(gn)であることを示し,総移動回数の点で漸近的に最適であるということを述べる. |
| 抄録(英) | In this paper we consider the partial rendezous of mobile agents in asynchronous rings , which requires, for a given input g, that each agent meets (g-1) agents in some node. We propose two algorithms to solve the partial rendezvous problem. One algorithm is deterministic and assumes unique ID of each agent. The other is randomized and assumes anonymous agents. The ditermistic algorithm requires the number of agents' moves O (gn),which is optimal, where n is the number of nodes. |
| キーワード(和) | 分散システム / モバイルエージェント / 集合問題 / 部分集合 |
| キーワード(英) | distributed system / mobile agent / rendezvous problem / partial rendezvous |
| 資料番号 | COMP2012-9 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2012/5/7(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 非同期リングにおけるモバイルエージェント部分集合アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Algorithms for partial rendezvous of mobile agents in asynchronous rings |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 分散システム / distributed system |
| キーワード(2)（和/英） | モバイルエージェント / mobile agent |
| キーワード(3)（和/英） | 集合問題 / rendezvous problem |
| キーワード(4)（和/英） | 部分集合 / partial rendezvous |
| 第 1 著者 氏名（和/英） | 柴田 将拡 / Masahiro SHIBATA |
| 第 1 著者 所属（和/英） | 大阪大学情報科学研究科 Information Science and Technology, Osaka University |
| 第 2 著者 氏名（和/英） | 川合 慎治 / Shinji KAWAI |
| 第 2 著者 所属（和/英） | 大阪大学情報科学研究科 Information Science and Technology, Osaka University |
| 第 3 著者 氏名（和/英） | 大下 福仁 / Fukuhito OOSHITA |
| 第 3 著者 所属（和/英） | 大阪大学情報科学研究科 Information Science and Technology, Osaka University |
| 第 4 著者 氏名（和/英） | 角川 裕次 / Hirotsugu KAKUGAWA |
| 第 4 著者 所属（和/英） | 大阪大学情報科学研究科 Information Science and Technology, Osaka University |
| 第 5 著者 氏名（和/英） | 増澤 利光 / Toshimitsu MASUZAWA |
| 第 5 著者 所属（和/英） | 大阪大学情報科学研究科 Information Science and Technology, Osaka University |
| 発表年月日 | 2012-05-14 |
| 資料番号 | COMP2012-9 |
| 巻番号（vol） | vol.112 |
| 号番号（no） | 24 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |