| アイテムタイプ |
会議発表論文 / Conference Paper(1) |
| 公開日 |
2024-06-14 |
| タイトル |
|
|
タイトル |
Partial Gathering of Mobile Agents in Dynamic Tori |
| 言語 |
|
|
言語 |
eng |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
distributed system |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
mobile agents |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
partial gathering |
| キーワード |
|
|
主題Scheme |
Other |
|
主題 |
dynamic tori |
| 資源タイプ |
|
|
資源タイプ |
conference paper |
| アクセス権 |
|
|
アクセス権 |
open access |
| 著者 |
Shibata, Masahiro
Kitamura, Naoki
江口, 僚太
Sudo, Yuichi
Nakamura, Junya
Kim, Yonghwan
|
| 抄録 |
|
|
内容記述タイプ |
Abstract |
|
内容記述 |
In this paper, we consider the partial gathering problem of mobile agents in synchronous dynamic tori. The partial gathering problem is a generalization of the (well-investigated) total gathering problem, which requires that all k agents distributed in the network terminate at a non-predetermined single node. The partial gathering problem requires, for a given positive integer g (< k), that agents terminate in a configuration such that either at least g agents or no agent exists at each node. So far, in almost cases, the partial gathering problem has been considered in static graphs. As only one exception, it is considered in a kind of dynamic rings called 1-interval connected rings, that is, one of the links in the ring may be missing at each time step. In this paper, we consider partial gathering in another dynamic topology. Concretely, we consider it in n× n dynamic tori such that each of row rings and column rings is represented as a 1-interval connected ring. In such networks, when k = O(gn), focusing on the relationship between the values of k, n, and g, we aim to characterize the solvability of the partial gathering problem and analyze the move complexity of the proposed algorithms when the problem can be solved. First, we show that agents cannot solve the problem when k = o(gn), which means that Ω (gn) agents are necessary to solve the problem. Second, we show that the problem can be solved with the total number of O(gn$00B3) moves when 2gn+2n-1 $2264 k $2264 2gn + 6n +16g -12. Finally, we show that the problem can be solved with the total number of O(gn$00B2) moves when k $2265 2gn + 6n +16g -11. From these results, we show that our algorithms can solve the partial gathering problem in dynamic tori with the asymptotically optimal number Θ (gn) of agents. In addition, we show that agents require a total number of Ω(gn$00B2) moves to solve the partial gathering problem in dynamic tori when k = Θ(gn). Thus, when k $2265 2gn+6n+16g -11, our algorithm can solve the problem with asymptotically optimal number O(gn$00B2) of agent moves. |
| 書誌情報 |
en : 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)
p. 2:1-2:22,
発行日 2023-06-12
|
| 会議情報 |
|
|
|
会議名 |
2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023) |
|
|
開始年 |
2023 |
|
|
開始月 |
06 |
|
|
開始日 |
19 |
|
|
終了年 |
2023 |
|
|
終了月 |
06 |
|
|
終了日 |
21 |
|
|
開催地 |
Pisa |
|
開催国 |
ITA |
| 出版者 |
|
|
出版者 |
Schloss Dagstuhl |
| ISSN |
|
|
収録物識別子タイプ |
EISSN |
|
収録物識別子 |
1868-8969 |
| 出版者版DOI |
|
|
関連タイプ |
isReplacedBy |
|
|
識別子タイプ |
DOI |
|
|
関連識別子 |
https://doi.org/10.4230/LIPIcs.SAND.2023.2 |
| 出版者版URI |
|
|
関連タイプ |
isReplacedBy |
|
|
識別子タイプ |
URI |
|
|
関連識別子 |
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.2 |
| 権利 |
|
|
権利情報Resource |
https://creativecommons.org/licenses/by/4.0/ |
|
権利情報 |
$00A9 Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim; licensed under Creative Commons License CC-BY 4.0 |
| 著者版フラグ |
|
|
出版タイプ |
NA |
