Time Optimal Distance-$k$-Dispersion on Dynamic Ring
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909293486276608 |
|---|---|
| author | Mondal, Brati Goswami, Pritam Sau, Buddhadeb |
| author_facet | Mondal, Brati Goswami, Pritam Sau, Buddhadeb |
| contents | Dispersion by mobile agents is a well studied problem in the literature on computing by mobile robots. In this problem, $l$ robots placed arbitrarily on nodes of a network having $n$ nodes are asked to relocate themselves autonomously so that each node contains at most $\lfloor \frac{l}{n}\rfloor$ robots. When $l\le n$, then each node of the network contains at most one robot. Recently, in NETYS'23, Kaur et al. introduced a variant of dispersion called \emph{Distance-2-Dispersion}. In this problem, $l$ robots have to solve dispersion with an extra condition that no two adjacent nodes contain robots.
In this work, we generalize the problem of Dispersion and Distance-2-Dispersion by introducing another variant called \emph{Distance-$k$-Dispersion (D-$k$-D)}. In this problem, the robots have to disperse on a network in such a way that shortest distance between any two pair of robots is at least $k$ and there exist at least one pair of robots for which the shortest distance is exactly $k$. Note that, when $k=1$ we have normal dispersion and when $k=2$ we have D-$2$-D. Here, we studied this variant for a dynamic ring (1-interval connected ring) for rooted initial configuration. We have proved the necessity of fully synchronous scheduler to solve this problem and provided an algorithm that solves D-$k$-D in $Θ(n)$ rounds under a fully synchronous scheduler. So, the presented algorithm is time optimal too. To the best of our knowledge, this is the first work that considers this specific variant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_12220 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Time Optimal Distance-$k$-Dispersion on Dynamic Ring Mondal, Brati Goswami, Pritam Sau, Buddhadeb Distributed, Parallel, and Cluster Computing Dispersion by mobile agents is a well studied problem in the literature on computing by mobile robots. In this problem, $l$ robots placed arbitrarily on nodes of a network having $n$ nodes are asked to relocate themselves autonomously so that each node contains at most $\lfloor \frac{l}{n}\rfloor$ robots. When $l\le n$, then each node of the network contains at most one robot. Recently, in NETYS'23, Kaur et al. introduced a variant of dispersion called \emph{Distance-2-Dispersion}. In this problem, $l$ robots have to solve dispersion with an extra condition that no two adjacent nodes contain robots. In this work, we generalize the problem of Dispersion and Distance-2-Dispersion by introducing another variant called \emph{Distance-$k$-Dispersion (D-$k$-D)}. In this problem, the robots have to disperse on a network in such a way that shortest distance between any two pair of robots is at least $k$ and there exist at least one pair of robots for which the shortest distance is exactly $k$. Note that, when $k=1$ we have normal dispersion and when $k=2$ we have D-$2$-D. Here, we studied this variant for a dynamic ring (1-interval connected ring) for rooted initial configuration. We have proved the necessity of fully synchronous scheduler to solve this problem and provided an algorithm that solves D-$k$-D in $Θ(n)$ rounds under a fully synchronous scheduler. So, the presented algorithm is time optimal too. To the best of our knowledge, this is the first work that considers this specific variant. |
| title | Time Optimal Distance-$k$-Dispersion on Dynamic Ring |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2408.12220 |