Beyond Rings: Gathering in 1-Interval Connected Graphs
Abstract
We examine the problem of gathering agents (or multi-agent rendezvous) in dynamic graphs which may change in every round. We consider a variant of the -interval connectivity model [9] in which all instances (snapshots) are always connected spanning subgraphs of an underlying graph, not necessarily a clique. The agents are identical and not equipped with explicit communication capabilities, and are initially arbitrarily positioned on the graph. The problem is for the agents to gather at the same node, not fixed in advance. We first show that the problem becomes impossible to solve if the underlying graph has a cycle. In light of this, we study a relaxed version of this problem, called weak gathering, where the agents are allowed to gather either at the same node, or at two adjacent nodes. Our goal is to characterize the class of 1-interval connected graphs and initial configurations in which the problem is solvable, both with and without homebases. On the negative side we show that when the underlying graph contains a spanning bicyclic subgraph and satisfies an additional connectivity property, weak gathering is unsolvable, thus we concentrate mainly on unicyclic graphs. As we show, in most instances of initial agent configurations, the agents must meet on the cycle. This adds an additional difficulty to the problem, as they need to explore the graph and recognize the nodes that form the cycle. We provide a deterministic algorithm for the solvable cases of this problem that runs in number of rounds.
Communicated by Andrew Adamatzky
References
- 1. , How to meet asynchronously (almost) everywhere, ACM Transactions on Algorithms (TALG) 8(4) (2012) 1–14. Crossref, ISI, Google Scholar
- 2. , Asynchronous deterministic rendezvous in graphs, Theor. Comput. Sci. 355(3) (2006) 315–326. Crossref, ISI, Google Scholar
- 3. ,
Deterministic rendezvous in graphs , in European Symposium on Algorithms (Springer, 2003), pp. 184–195. Crossref, Google Scholar - 4. , Move-optimal partial gathering of mobile agents without identifiers or global knowledge in asynchronous unidirectional rings, Theoretical Computer Science 822 (2020) 92–109. Crossref, ISI, Google Scholar
- 5. , The power of tokens: Rendezvous and symmetry detection for two mobile agents in a ring, in International Conference on Current Trends in Theory and Practice of Computer Science (Springer, 2008), pp. 234–246. Crossref, Google Scholar
- 6. , Rendezvous and election of mobile agents: impact of sense of direction, Theory of Computing Systems 40(2) (2007) 143–162. Crossref, ISI, Google Scholar
- 7. , Rendezvous of mobile agents in unknown graphs with faulty links, in International Symposium on Distributed Computing (Springer, 2007), pp. 108–122. Crossref, Google Scholar
- 8. , Gathering in dynamic rings, Theoretical Computer Science 811 (2020) 79–98. Crossref, ISI, Google Scholar
- 9. , Distributed computation in dynamic networks, in Proceedings of the 42nd ACM symposium on Theory of Computing (STOC) (ACM, 2010), pp. 513–522. Crossref, Google Scholar
- 10. , Live exploration of dynamic rings, in 36th International Conference on Distributed Computing Systems (ICDCS) (IEEE, 2016), pp. 570–579. Crossref, Google Scholar
- 11. , Broadcasting with mobile agents in dynamic networks, in 24th International Conference on Principles of Distributed Systems (OPODIS 2020) (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021). Google Scholar
- 12. , Group exploration of dynamic tori, in 38th International Conference on Distributed Computing Systems (ICDCS) (IEEE, 2018), pp. 775–785. Crossref, Google Scholar
- 13. , Tight bounds on distributed exploration of temporal graphs, in 23rd International Conference on Principles of Distributed Systems (OPODIS 2019) (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020). Google Scholar
- 14. , The mobile agent rendezvous problem in the ring, Synthesis Lectures on Distributed Computing Theory 1(1) (2010) 1–122. Crossref, Google Scholar
- 15. , Deterministic rendezvous in networks: A comprehensive survey, Networks 59(3) (2012) 331–347. Crossref, ISI, Google Scholar
- 16. , Deterministic rendezvous in graphs, Algorithmica 46(1) (2006) 69–96. Crossref, ISI, Google Scholar
- 17. , Mobile agents in distributed computing: Network exploration, Bulletin of EATCS 1(109) (2013). Google Scholar
- 18. , Distributed exploration of an unknown graph, in International Colloquium on Structural Information and Communication Complexity (Springer, 2005), pp. 99–114. Crossref, Google Scholar
- 19. , Map construction of unknown graphs by multiple agents, Theoretical Computer Science 385(1–3) (2007) 34–48. Crossref, ISI, Google Scholar
- 20. , Multi-agent deterministic graph mapping via robot rendezvous, in International Conference on Robotics and Automation (IEEE, 2012), pp. 1278–1283. Crossref, Google Scholar
- 21. , Exploring unknown undirected graphs, in Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (Society for Industrial and Applied Mathematics, 1998), pp. 316–322. Google Scholar
- 22. , Time-varying graphs and dynamic networks, International Journal of Parallel, Emergent and Distributed Systems 27(5) (2012) 387–408. Crossref, Google Scholar
- 23. , Causality, influence, and computation in possibly disconnected synchronous dynamic networks, Journal of Parallel and Distributed Computing 74(1) (2014) 2016–2026. Crossref, ISI, Google Scholar


