Abstract
We consider the Gathering problem where a swarm of weak robots disposed on the vertices of an anonymous graph are required to meet at one vertex from where they do not move anymore. In our recent work [Cicerone et al., SIROCCO’19], we have shown how synchronicity heavily affects the design of resolution algorithms within the standard Look-Compute-Move (LCM) model. In particular, we have investigated two dense and highly symmetric topologies: complete graphs and complete bipartite graphs. We characterized all solvable configurations for synchronous robots, whereas it is known that in complete graphs asynchronous robots cannot solve the problem, ever. Instead of approaching directly the asynchronous case in complete bipartite graphs, we asked what happens in the so-called semi-synchronous model, that is robots are synchronized but they are not necessarily all active within all LCM cycles. It turns out that still the gathering can never be accomplished on complete graphs, whereas challenging cases arise in complete bipartite graphs. We provide a distributed algorithm solving the problem for a wide set of possible configurations. For most of the remaining ones instead we provide impossibility results and a few of ad hoc resolution algorithms studied for very specific cases. Over all, still a full characterization is missing but our study points out how difficult might be to derive a general argument that catches all peculiarities. Moreover, some of our approaches reveal new insights that might be very useful for the resolution of other tasks.
The work has been supported in part by the European project “Geospatial based Environment for Optimisation Systems Addressing Fire Emergencies” (GEO-SAFE), contract no. H2020-691161, and by the Italian National Group for Scientific Computation (GNCS-INdAM).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bose, K., Kundu, M.K., Adhikary, R., Sau, B.: Optimal gathering by asynchronous oblivious robots in hypercubes. In: Gilbert, S., Hughes, D., Krishnamachari, B. (eds.) ALGOSENSORS 2018. LNCS, vol. 11410, pp. 102–117. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-14094-6_7
Cicerone, S., Di Stefano, G., Navarra, A.: MinMax-distance gathering on given meeting points. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 127–139. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-18173-8_9
Cicerone, S., Di Stefano, G., Navarra, A.: Gathering of robots on meeting-points: feasibility and optimal resolution algorithms. Distrib. Comput. 31(1), 1–50 (2018)
Cicerone, S., Di Stefano, G., Navarra, A.: Asynchronous arbitrary pattern formation: the effects of a rigorous approach. Distrib. Comput. 32(2), 91–132 (2019)
Cicerone, S., Di Stefano, G., Navarra, A.: Asynchronous robots on graphs: gathering. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities. Lecture Notes in Computer Science, vol. 11340, pp. 184–217. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7_8
Cicerone, S., Di Stefano, G., Navarra, A.: Gathering synchronous robots in graphs: from general properties to dense and symmetric topologies. In: Censor-Hillel, K., Flammini, M. (eds.) SIROCCO 2019. LNCS, vol. 11639, pp. 170–184. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-24922-9_12
Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: gathering. SIAM J. Comput. 41(4), 829–879 (2012)
D’Angelo, G., Di Stefano, G., Klasing, R., Navarra, A.: Gathering of robots on anonymous grids and trees without multiplicity detection. Theor. Comput. Sci. 610, 158–168 (2016)
D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering on rings under the look-compute-move model. Distrib. Comput. 27(4), 255–285 (2014)
D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering six oblivious robots on anonymous symmetric rings. J. Discret. Algorithms 26, 16–27 (2014)
D’Angelo, G., Di Stefano, G., Navarra, A., Nisse, N., Suchan, K.: Computing on rings by oblivious robots: a unified approach for different tasks. Algorithmica 72(4), 1055–1096 (2015)
D’Angelo, G., Navarra, A., Nisse, N.: A unified approach for gathering and exclusive searching on rings under weak assumptions. Distrib. Comput. 30(1), 17–48 (2017)
D’Emidio, M., Di Stefano, G., Frigioni, D., Navarra, A.: Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane. Inf. Comput. 263, 57–74 (2018)
Di Stefano, G., Navarra, A.: Gathering of oblivious robots on infinite grids with minimum traveled distance. Inf. Comput. 254, 377–391 (2017)
Di Stefano, G., Navarra, A.: Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings. Distrib. Comput. 30(2), 75–86 (2017)
Guilbault, S., Pelc, A.: Gathering asynchronous oblivious agents with local vision in regular bipartite graphs. Theor. Comput. Sci. 509, 86–96 (2013)
Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Time-optimal gathering algorithm of mobile robots with local weak multiplicity detection in rings. IEICE Trans. 96–A(6), 1072–1080 (2013)
Klasing, R., Kosowski, A., Navarra, A.: Taking advantage of symmetries: gathering of many asynchronous oblivious robots on a ring. Theor. Comput. Sci. 411, 3235–3246 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Cicerone, S., Di Stefano, G., Navarra, A. (2019). On Gathering of Semi-synchronous Robots in Graphs. In: Ghaffari, M., Nesterenko, M., Tixeuil, S., Tucci, S., Yamauchi, Y. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2019. Lecture Notes in Computer Science(), vol 11914. Springer, Cham. https://doi.org/10.1007/978-3-030-34992-9_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-34992-9_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-34991-2
Online ISBN: 978-3-030-34992-9
eBook Packages: Computer ScienceComputer Science (R0)