License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAND.2023.2
URN: urn:nbn:de:0030-drops-179387
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17938/
Shibata, Masahiro ;
Kitamura, Naoki ;
Eguchi, Ryota ;
Sudo, Yuichi ;
Nakamura, Junya ;
Kim, Yonghwan
Partial Gathering of Mobile Agents in Dynamic Tori
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³) moves when 2gn+2n-1 ≤ k ≤ 2gn + 6n +16g -12. Finally, we show that the problem can be solved with the total number of O(gn²) moves when k ≥ 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²) moves to solve the partial gathering problem in dynamic tori when k = Θ(gn). Thus, when k ≥ 2gn+6n+16g -11, our algorithm can solve the problem with asymptotically optimal number O(gn²) of agent moves.
BibTeX - Entry
@InProceedings{shibata_et_al:LIPIcs.SAND.2023.2,
author = {Shibata, Masahiro and Kitamura, Naoki and Eguchi, Ryota and Sudo, Yuichi and Nakamura, Junya and Kim, Yonghwan},
title = {{Partial Gathering of Mobile Agents in Dynamic Tori}},
booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
pages = {2:1--2:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-275-4},
ISSN = {1868-8969},
year = {2023},
volume = {257},
editor = {Doty, David and Spirakis, Paul},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17938},
URN = {urn:nbn:de:0030-drops-179387},
doi = {10.4230/LIPIcs.SAND.2023.2},
annote = {Keywords: distributed system, mobile agents, partial gathering, dynamic tori}
}
|
Keywords: |
|
distributed system, mobile agents, partial gathering, dynamic tori |
|
Collection: |
|
2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
12.06.2023 |
