World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Beyond Rings: Gathering in 1-Interval Connected Graphs

    We examine the problem of gathering k2 agents (or multi-agent rendezvous) in dynamic graphs which may change in every round. We consider a variant of the 1-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 O(n2+nk) number of rounds.

    Communicated by Andrew Adamatzky

    References

    • 1. J. Czyzowicz, A. Pelc and A. Labourel, How to meet asynchronously (almost) everywhere, ACM Transactions on Algorithms (TALG) 8(4) (2012) 1–14. Crossref, ISIGoogle Scholar
    • 2. G. De Marco, L. Gargano, E. Kranakis, D. Krizanc, A. Pelc and U. Vaccaro, Asynchronous deterministic rendezvous in graphs, Theor. Comput. Sci. 355(3) (2006) 315–326. Crossref, ISIGoogle Scholar
    • 3. A. Dessmark, P. Fraigniaud and A. Pelc, Deterministic rendezvous in graphs, in European Symposium on Algorithms (Springer, 2003), pp. 184–195. CrossrefGoogle Scholar
    • 4. M. Shibata, N. Kawata, Y. Sudo, F. Ooshita, H. Kakugawa and T. Masuzawa, Move-optimal partial gathering of mobile agents without identifiers or global knowledge in asynchronous unidirectional rings, Theoretical Computer Science 822 (2020) 92–109. Crossref, ISIGoogle Scholar
    • 5. J. Czyzowicz, S. Dobrev, E. Kranakis and D. Krizanc, 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. CrossrefGoogle Scholar
    • 6. L. Barriere, P. Flocchini, P. Fraigniaud and N. Santoro, Rendezvous and election of mobile agents: impact of sense of direction, Theory of Computing Systems 40(2) (2007) 143–162. Crossref, ISIGoogle Scholar
    • 7. J. Chalopin, S. Das and N. Santoro, Rendezvous of mobile agents in unknown graphs with faulty links, in International Symposium on Distributed Computing (Springer, 2007), pp. 108–122. CrossrefGoogle Scholar
    • 8. G. A. Di Luna, P. Flocchini, L. Pagli, G. Prencipe, N. Santoro and G. Viglietta, Gathering in dynamic rings, Theoretical Computer Science 811 (2020) 79–98. Crossref, ISIGoogle Scholar
    • 9. F. Kuhn, N. Lynch and R. Oshman, Distributed computation in dynamic networks, in Proceedings of the 42nd ACM symposium on Theory of Computing (STOC) (ACM, 2010), pp. 513–522. CrossrefGoogle Scholar
    • 10. G. A. Di Luna, S. Dobrev, P. Flocchini and N. Santoro, Live exploration of dynamic rings, in 36th International Conference on Distributed Computing Systems (ICDCS) (IEEE, 2016), pp. 570–579. CrossrefGoogle Scholar
    • 11. S. Das, N. Giachoudis, F. L. Luccio and E. Markou, 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. T. Gotoh, Y. Sudo, F. Ooshita, H. Kakugawa and T. Masuzawa, Group exploration of dynamic tori, in 38th International Conference on Distributed Computing Systems (ICDCS) (IEEE, 2018), pp. 775–785. CrossrefGoogle Scholar
    • 13. T. Gotoh, P. Flocchini, T. Masuzawa and N. Santoro, 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. E. Kranakis, D. Krizanc and E. Markou, The mobile agent rendezvous problem in the ring, Synthesis Lectures on Distributed Computing Theory 1(1) (2010) 1–122. CrossrefGoogle Scholar
    • 15. A. Pelc, Deterministic rendezvous in networks: A comprehensive survey, Networks 59(3) (2012) 331–347. Crossref, ISIGoogle Scholar
    • 16. A. Dessmark, P. Fraigniaud, D. R. Kowalski and A. Pelc, Deterministic rendezvous in graphs, Algorithmica 46(1) (2006) 69–96. Crossref, ISIGoogle Scholar
    • 17. S. Das, Mobile agents in distributed computing: Network exploration, Bulletin of EATCS 1(109) (2013). Google Scholar
    • 18. S. Das, P. Flocchini, A. Nayak and N. Santoro, Distributed exploration of an unknown graph, in International Colloquium on Structural Information and Communication Complexity (Springer, 2005), pp. 99–114. CrossrefGoogle Scholar
    • 19. S. Das, P. Flocchini, S. Kutten, A. Nayak and N. Santoro, Map construction of unknown graphs by multiple agents, Theoretical Computer Science 385(1–3) (2007) 34–48. Crossref, ISIGoogle Scholar
    • 20. C. Gong, S. Tully, G. Kantor and H. Choset, Multi-agent deterministic graph mapping via robot rendezvous, in International Conference on Robotics and Automation (IEEE, 2012), pp. 1278–1283. CrossrefGoogle Scholar
    • 21. P. Panaite and A. Pelc, 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. A. Casteigts, P. Flocchini, W. Quattrociocchi and N. Santoro, Time-varying graphs and dynamic networks, International Journal of Parallel, Emergent and Distributed Systems 27(5) (2012) 387–408. CrossrefGoogle Scholar
    • 23. O. Michail, I. Chatzigiannakis and P. G. Spirakis, Causality, influence, and computation in possibly disconnected synchronous dynamic networks, Journal of Parallel and Distributed Computing 74(1) (2014) 2016–2026. Crossref, ISIGoogle Scholar