Simulating Chirality: Solving Distance-$k$-Dispersion on an 1-Interval Connected Ring
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912492791267328 |
|---|---|
| author | Mondal, Brati Goswami, Pritam Sau, Buddhadeb |
| author_facet | Mondal, Brati Goswami, Pritam Sau, Buddhadeb |
| contents | We study the Distance-$k$-Dispersion (D-$k$-D) problem for synchronous mobile agents in a 1-interval-connected ring network having $n$ nodes and with $l$ agents where $3 \le l \le \lfloor \frac{n}{k}\rfloor$, without the assumption of chirality (a common sense of direction for the agents). This generalizes the classical dispersion problem by requiring that agents maintain a minimum distance of $k$ hops from each other, with the special case $k=1$ corresponding to the standard dispersion.
The contribution in this work is threefold. Our first contribution is a novel method that enables agents to simulate chirality using only local information, vision and bounded memory. This technique demonstrates that chirality is not a fundamental requirement for coordination in this model.
Building on this, our second contribution partially resolves an open question posed by Agarwalla et al. (ICDCN, 2018), who considered the same model (1- interval connected ring, synchronous agents, no chirality). We prove that D-$k$-D, and thus dispersion is solvable from any arbitrary configuration under these assumptions (excluding vertex permutation dynamism)for any size of the ring network which was earlier limited to only odd sized ring or to a ring of size four.
Finally, we present an algorithm for D-$k$-D in this setting that works in $O(ln)$ rounds, completing the constructive side of our result.
Altogether, our findings significantly extend the theoretical understanding of mobile agent coordination in dynamic networks and clarify the role of chirality in distributed computation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_14723 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Simulating Chirality: Solving Distance-$k$-Dispersion on an 1-Interval Connected Ring Mondal, Brati Goswami, Pritam Sau, Buddhadeb Distributed, Parallel, and Cluster Computing We study the Distance-$k$-Dispersion (D-$k$-D) problem for synchronous mobile agents in a 1-interval-connected ring network having $n$ nodes and with $l$ agents where $3 \le l \le \lfloor \frac{n}{k}\rfloor$, without the assumption of chirality (a common sense of direction for the agents). This generalizes the classical dispersion problem by requiring that agents maintain a minimum distance of $k$ hops from each other, with the special case $k=1$ corresponding to the standard dispersion. The contribution in this work is threefold. Our first contribution is a novel method that enables agents to simulate chirality using only local information, vision and bounded memory. This technique demonstrates that chirality is not a fundamental requirement for coordination in this model. Building on this, our second contribution partially resolves an open question posed by Agarwalla et al. (ICDCN, 2018), who considered the same model (1- interval connected ring, synchronous agents, no chirality). We prove that D-$k$-D, and thus dispersion is solvable from any arbitrary configuration under these assumptions (excluding vertex permutation dynamism)for any size of the ring network which was earlier limited to only odd sized ring or to a ring of size four. Finally, we present an algorithm for D-$k$-D in this setting that works in $O(ln)$ rounds, completing the constructive side of our result. Altogether, our findings significantly extend the theoretical understanding of mobile agent coordination in dynamic networks and clarify the role of chirality in distributed computation. |
| title | Simulating Chirality: Solving Distance-$k$-Dispersion on an 1-Interval Connected Ring |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2507.14723 |