WEKO3
アイテム
Partial gathering of mobile agents in asynchronous unidirectional rings
http://hdl.handle.net/10061/11097
http://hdl.handle.net/10061/11097d550364a-c8d0-4d68-92fe-17989ea8f09c
名前 / ファイル | ライセンス | アクション |
---|---|---|
fulltext (456.3 kB)
|
|
Item type | 学術雑誌論文 / Journal Article(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2017-09-25 | |||||
タイトル | ||||||
タイトル | Partial gathering of mobile agents in asynchronous unidirectional rings | |||||
言語 | en | |||||
言語 | ||||||
言語 | eng | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | Distributed system | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | Mobile agent | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | Gathering problem | |||||
キーワード | ||||||
言語 | en | |||||
主題Scheme | Other | |||||
主題 | Partial gathering | |||||
資源タイプ | ||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
資源タイプ | journal article | |||||
アクセス権 | ||||||
アクセス権 | open access | |||||
アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||
著者 |
Shibata, Masahiro
× Shibata, Masahiro× Kawai, Shinji× Ooshita, Fukuhito× Kakugawa, Hirotsugu× Masuzawa, Toshimitsu |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | In this paper, we consider the partial gathering problem of mobile agents in asynchronous unidirectional rings equipped with whiteboards on nodes. The partial gathering problem is a new generalization of the total gathering problem. The partial gathering problem requires, for a given integer g, that each agent should move to a node and terminate so that at least g agents should meet at the same node. The requirement for the partial gathering problem is weaker than that for the (well-investigated) total gathering problem, and thus, we have interests in clarifying the difference on the move complexity between them. We propose three algorithms to solve the partial gathering problem. The first algorithm is deterministic but requires unique ID of each agent. This algorithm achieves the partial gathering in O(gn)O(gn) total moves, where n is the number of nodes. The second algorithm is randomized and requires no unique ID of each agent (i.e., anonymous). This algorithm achieves the partial gathering in expected O(gn)O(gn) total moves. The third algorithm is deterministic and requires no unique ID of each agent. For this case, we show that there exist initial configurations in which no algorithm can solve the problem and agents can achieve the partial gathering in O(kn)O(kn) total moves for solvable initial configurations, where k is the number of agents. Note that the total gathering problem requires Ω(kn)Ω(kn) total moves, while the partial gathering problem requires Ω(gn)Ω(gn) total moves in each model. Hence, we show that the move complexity of the first and second algorithms is asymptotically optimal. | |||||
言語 | en | |||||
書誌情報 |
en : Theoretical Computer Science 巻 617, p. 1-11, 発行日 2015-09-25 |
|||||
出版者 | ||||||
出版者 | Elsevier | |||||
言語 | en | |||||
ISSN | ||||||
収録物識別子タイプ | ISSN | |||||
収録物識別子 | 0304-3975 | |||||
出版者版DOI | ||||||
関連タイプ | isIdenticalTo | |||||
識別子タイプ | DOI | |||||
関連識別子 | https://doi.org/10.1016/j.tcs.2015.09.012 | |||||
収録物識別子 | ||||||
収録物識別子タイプ | NCID | |||||
収録物識別子 | AA00862688 | |||||
権利 | ||||||
言語 | ja | |||||
権利情報 | 出版社許諾条件により本文は2017/09/25以降に公表。 | |||||
権利 | ||||||
言語 | en | |||||
権利情報 | Copyright c 2015 The Authors | |||||
著者版フラグ | ||||||
出版タイプ | VoR | |||||
出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 |