×

Gathering in dynamic rings. (English) Zbl 1437.68195

Summary: The gathering (or multi-agent rendezvous) problem requires a set of mobile agents, arbitrarily positioned at different nodes of a network to group within finite time at the same location, not fixed in advanced.
The extensive existing literature on this problem shares the same fundamental assumption: the topological structure does not change during the rendezvous or the gathering; this is true also for those investigations that consider faulty nodes. In other words, they only consider static graphs.
In this paper we start the investigation of gathering in dynamic graphs, that is networks where the topology changes continuously and at unpredictable locations.
We study the feasibility of gathering mobile agents, identical and without explicit communication capabilities, in a dynamic ring of anonymous nodes; the class of dynamics we consider is the classic 1-interval-connectivity; i.e., dynamic graphs that are however connected at any point in time. We focus on the impact that factors such as chirality (i.e., a common sense of orientation) and cross detection (i.e., the ability to detect, when traversing an edge, whether some agent is traversing it in the other direction), have on the solvability of the problem; and we establish several results.
We provide a complete characterization of the classes of initial configurations from which the gathering problem is solvable in presence and in absence of cross detection and of chirality. The feasibility results of the characterization are all constructive: we provide distributed algorithms that allow the agents to gather within low polynomial time. In particular, the algorithms for gathering with cross detection are time optimal. We also show that cross detection is a powerful computational element. Indeed, we prove that, without chirality, knowledge of the ring size \(n\) is strictly more powerful than knowledge of the number \(k\) of agents; on the other hand, with chirality, knowledge of \(n\) can be substituted by knowledge of \(k\), yielding the same classes of feasible initial configurations.
From our investigation it follows that, for the gathering problem, the computational obstacles created by the dynamic nature of the ring can be overcome by the presence of chirality or of cross-detection.

MSC:

68W15 Distributed algorithms
68M14 Distributed systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alpern, S.; Gal, S., The Theory of Search Games and Rendezvous (2003), Kluwer · Zbl 1034.91017
[2] Barrière, L.; Flocchini, P.; Fraigniaud, P.; Santoro, N., Rendezvous and election of mobile agents: impact of sense of direction, Theory Comput. Syst., 44, 3, 143-162 (2007) · Zbl 1107.68022
[3] Baston, V.; Gal, S., Rendezvous search when marks are left at the starting points, Naval Res. Logist., 38, 469-494 (1991)
[4] Biely, M.; Robinson, P.; Schmid, U.; Schwarz, M.; Winkler, K., Gracefully degrading consensus and k-set agreement in directed dynamic networks, (Proc. 2nd International Conference on Networked Systems. Proc. 2nd International Conference on Networked Systems, NETSYS (2015)), 109-124
[5] Bouchard, S.; Dieudonne, Y.; Ducourthial, B., Byzantine gathering in networks, Distrib. Comput., 29, 6, 435-457 (2016) · Zbl 1412.68021
[6] Bournat, M.; Datta, A.; Dubois, S., Self-stabilizing robots in highly dynamic environments, (Proc. 18th International Symposium on Stabilization, Safety, and Security of Distributed System. Proc. 18th International Symposium on Stabilization, Safety, and Security of Distributed System, SSS (2016)), 54-69 · Zbl 1425.68411
[7] Casteigts, A.; Flocchini, P.; Mans, B.; Santoro, N., Measuring temporal lags in delay-tolerant networks, IEEE Trans. Comput., 63, 2, 397-410 (2014) · Zbl 1364.68049
[8] Casteigts, A.; Flocchini, P.; Quattrociocchi, W.; Santoro, N., Time-varying graphs and dynamic networks, Int. J. Parallel Emergent Distrib. Syst., 27, 5, 387-408 (2012)
[9] Chalopin, J.; Das, S.; Santoro, N., Rendezvous of mobile agents in unknown graphs with faulty links, (Proc. 21st International Symposium on Distributed Computing. Proc. 21st International Symposium on Distributed Computing, DISC (2007)), 108-122 · Zbl 1145.68347
[10] Cieliebak, M.; Flocchini, P.; Prencipe, G.; Santoro, N., Distributed computing by mobile robots: gathering, SIAM J. Comput., 41, 4, 829-879 (2012) · Zbl 1286.68484
[11] Cohen, R.; Peleg, D., Convergence properties of the gravitational algorithm in asynchronous robot systems, SIAM J. Comput., 34, 1516-1528 (2005) · Zbl 1081.68110
[12] Czyzowicz, J.; Dobrev, S.; Kranakis, E.; Krizanc, D., The power of tokens: rendezvous and symmetry detection for two mobile agents in a ring, (Proc. 34th Conference on Current Trends in Theory and Practice of Computer Science. Proc. 34th Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM (2008)), 234-246 · Zbl 1132.68695
[13] Czyzowicz, J.; Labourel, A.; Pelc, A., How to meet asynchronously (almost) everywhere, ACM Trans. Algorithms, 8, 4, 37:1-37:14 (2012) · Zbl 1295.68171
[14] Das, S.; Luccio, F. L.; Focardi, R.; Markou, E.; Moro, D.; Squarcina, M., Gathering of robots in a ring with mobile faults, (Proc. 17th Italian Conference on Theoretical Computer Science. Proc. 17th Italian Conference on Theoretical Computer Science, ICTCS (2016)), 122-135
[15] Das, S.; Luccio, F. L.; Markou, E., Mobile agents rendezvous in spite of a malicious agent, (Proc. 11th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics. Proc. 11th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS (2015)), 211-224
[16] De Marco, G.; Gargano, L.; Kranakis, E.; Krizanc, D.; Pelc, A.; Vaccaro, U., Asynchronous deterministic rendezvous in graphs, Theoret. Comput. Sci., 355, 315-326 (2006) · Zbl 1088.68140
[17] Degener, B.; Kempkes, B.; Langner, T.; Meyer auf der Heide, F.; Pietrzyk, P.; Wattenhofer, R., A tight runtime bound for synchronous gathering of autonomous robots with limited visibility, (Proc. 23rd ACM Symposium on Parallelism in Algorithms and Architectures. Proc. 23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA (2011)), 139-148
[18] Di Luna, G. A.; Baldoni, R., Brief announcement: investigating the cost of anonymity on dynamic networks, (Proc of the 34th Symposium on Principles of Distributed Computing. Proc of the 34th Symposium on Principles of Distributed Computing, PODC (2015)), 339-341
[19] Di Luna, G. A.; Baldoni, R.; Bonomi, S.; Chatzigiannakis, I., Counting in anonymous dynamic networks under worst-case adversary, (Proc. of the IEEE 34th International Conference on Distributed Computing Systems. Proc. of the IEEE 34th International Conference on Distributed Computing Systems, ICDCS (2014)), 338-347
[20] Di Luna, G. A.; Dobrev, S.; Flocchini, P.; Santoro, N., Live exploration of dynamic rings, (Proc. 36th IEEE International Conference on Distributed Computing Systems. Proc. 36th IEEE International Conference on Distributed Computing Systems, ICDCS (2016)), 570-579
[21] Di Luna, G. A.; Flocchini, P.; Pagli, L.; Prencipe, G.; Santoro, N.; Viglietta, G., Gathering in dynamic rings, (Proc. of the 24th International Colloquium on Structural Information and Communication Complexity. Proc. of the 24th International Colloquium on Structural Information and Communication Complexity, SIROCCO (2017)), 339-355 · Zbl 1437.68194
[22] Dobrev, S.; Flocchini, P.; Prencipe, G.; Santoro, N., Multiple agents rendezvous in a ring in spite of a black hole, (Proc. 7th International Conference on Principles of Distributed Systems. Proc. 7th International Conference on Principles of Distributed Systems, OPODIS (2003)), 34-46 · Zbl 1078.68564
[23] Flocchini, P.; Kranakis, E.; Krizanc, D.; Luccio, F. L.; Santoro, N., Sorting multisets in anonymous asynchronous rings, J. Parallel Distrib. Comput., 64, 2, 254-265 (2004) · Zbl 1069.68023
[24] Flocchini, P.; Kranakis, E.; Krizanc, D.; Santoro, N.; Sawchuk, C., Multiple mobile agent rendezvous in the ring, (Proc. 6th Latin American Conference on Theoretical Informatics. Proc. 6th Latin American Conference on Theoretical Informatics, LATIN (2004)), 599-608 · Zbl 1196.68021
[25] Flocchini, P.; Prencipe, G.; Santoro, N.; Widmayer, P., Gathering of asynchronous robots with limited visibility, Theoret. Comput. Sci., 337, 1-3, 147-168 (2005) · Zbl 1108.68120
[26] Flocchini, P.; Santoro, N.; Viglietta, G.; Yamashita, M., Rendezvous with constant memory, Theoret. Comput. Sci., 621, 57-72 (2016) · Zbl 1335.68278
[27] Haeupler, B.; Kuhn, F., Lower bounds on information dissemination in dynamic networks, (Proc. 26th International Symposium on Distributed Computing. Proc. 26th International Symposium on Distributed Computing, DISC (2012)), 166-180 · Zbl 1377.68021
[28] Ilcinkas, D.; Klasing, R.; Wade, A., Exploration of constantly connected dynamic graphs based on cactuses, (Proc. 21st Int. Coll. Structural Inform. and Comm. Complexity. Proc. 21st Int. Coll. Structural Inform. and Comm. Complexity, SIROCCO (2014)), 250-262 · Zbl 1416.68192
[29] Ilcinkas, D.; Wade, A., Exploration of the t-interval-connected dynamic graphs: the case of the ring, (Proc. 20th Int. Coll. on Structural Inform. and Comm. Complexity. Proc. 20th Int. Coll. on Structural Inform. and Comm. Complexity, SIROCCO (2013)), 13-23 · Zbl 1362.68022
[30] Klasing, R.; Markou, E.; Pelc, A., Gathering asynchronous oblivious mobile robots in a ring, Theoret. Comput. Sci., 390, 1, 27-39 (2008) · Zbl 1134.68013
[31] Kranakis, E.; Krizanc, D.; Markou, E., Mobile agent rendezvous in a synchronous torus, (7th Latin American Conference on Theoretical Informatics. 7th Latin American Conference on Theoretical Informatics, LATIN (2006)), 653-664 · Zbl 1145.68330
[32] Kranakis, E.; Krizanc, D.; Markou, E., The Mobile Agent Rendezvous Problem in the Ring (2010), Morgan & Claypool
[33] Kranakis, E.; Krizanc, D.; Santoro, N.; Sawchuk, C., Mobile agent rendezvous problem in the ring, (Proc. 23rd International Conference on Distributed Computing Systems. Proc. 23rd International Conference on Distributed Computing Systems, ICDCS (2003)), 592-599
[34] Kuhn, F.; Lynch, N.; Oshman, R., Distributed computation in dynamic networks, (Proc. 42nd Symposium on Theory of Computing. Proc. 42nd Symposium on Theory of Computing, STOC (2010)), 513-522 · Zbl 1293.68305
[35] Kuhn, F.; Moses, Y.; Oshman, R., Coordinated consensus in dynamic networks, (Proc. 30th Symposium on Principles of Distributed Computing. Proc. 30th Symposium on Principles of Distributed Computing, PODC (2011)), 1-10 · Zbl 1321.68028
[36] Lin, J.; Morse, A.; Anderson, B., The multi-agent rendezvous problem. Parts 1 and 2, SIAM J. Control Optim., 46, 6, 2096-2147 (2007) · Zbl 1149.93023
[37] Pagli, L.; Prencipe, G.; Viglietta, G., Getting close without touching: near-gathering for autonomous mobile robots, Distrib. Comput., 28, 5, 333-349 (2015) · Zbl 1341.68280
[38] Pelc, A., Deterministic rendezvous in networks: a comprehensive survey, Networks, 59, 3, 331-347 (2012)
[39] Sawchuk, C., Mobile Agent Rendezvous in the Ring (January 2004), Carleton University, Ph.D. Thesis
[40] Ta-Shma, A.; Zwick, U., Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences, ACM Trans. Algorithms, 10, 3 (2014) · Zbl 1333.68216
[41] Yu, X.; Yung, M., Agent rendezvous: a dynamic symmetry-breaking problem, (Proc. International Colloquium on Automata, Languages, and Programming. Proc. International Colloquium on Automata, Languages, and Programming, ICALP (1996)), 610-621 · Zbl 1046.68535
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.