Skip to main content
Erschienen in: Distributed Computing 4/2014

01.08.2014

Gathering on rings under the Look–Compute–Move model

verfasst von: Gianlorenzo D’Angelo, Gabriele Di Stefano, Alfredo Navarra

Erschienen in: Distributed Computing | Ausgabe 4/2014

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A set of robots arbitrarily placed on different nodes of an anonymous ring have to meet at one common node and there remain. This problem is known in the literature as the gathering. Anonymous and oblivious robots operate in Look–Compute–Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move). Cycles are asynchronous among robots. Moreover, each robot is empowered by the so called multiplicity detection capability, that is, it is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. The described problem has been extensively studied during the last years. However, the known solutions work only for specific initial configurations and leave some open cases. In this paper, we provide an algorithm which solves the general problem but for few marginal and specific cases, and is able to detect all the ungatherable configurations. It is worth noting that our new algorithm makes use of some previous techniques and unifies them with new strategies in order to deal with any initial configuration, even those left open by previous works.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Such an odd interval always exists. In fact, if the axis of symmetry passes through two even intervals the configuration has an edge–edge symmetry which is ungatherable.
 
2
Actually the graphical descriptions contained in “Appendix 1” can be exploited by the reader for all configuration types and hence from now on we do not point again to such appendix.
 
Literatur
2.
Zurück zum Zitat Bampas, E., Czyzowicz, J., Gasieniec, L., Ilcinkas, D., Labourel, A.: Almost optimal asynchronous rendezvous in infinite multidimensional grids. In: Proceedings of the 24th Internatioanal Symposium on Distributed Computing (DISC), Lecture Notes in Computer Science, vol. 6343, pp. 297–311 (2010) Bampas, E., Czyzowicz, J., Gasieniec, L., Ilcinkas, D., Labourel, A.: Almost optimal asynchronous rendezvous in infinite multidimensional grids. In: Proceedings of the 24th Internatioanal Symposium on Distributed Computing (DISC), Lecture Notes in Computer Science, vol. 6343, pp. 297–311 (2010)
3.
Zurück zum Zitat Blin, L., Burman, J., Nisse, N.: Exclusive graph searching. In: Proceedings of the 21st Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, vol. 8125, pp. 181–192 (2013) Blin, L., Burman, J., Nisse, N.: Exclusive graph searching. In: Proceedings of the 21st Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, vol. 8125, pp. 181–192 (2013)
4.
Zurück zum Zitat Blin, L., Milani, A., Potop-Butucaru, M., Tixeuil, S.: Exclusive perpetual ring exploration without chirality. In: Procedings of the 24th International Symposium on Distributed Computing (DISC), Lecture Notes in Computer Science, vol. 6343, pp. 312–327. Springer (2010) Blin, L., Milani, A., Potop-Butucaru, M., Tixeuil, S.: Exclusive perpetual ring exploration without chirality. In: Procedings of the 24th International Symposium on Distributed Computing (DISC), Lecture Notes in Computer Science, vol. 6343, pp. 312–327. Springer (2010)
5.
Zurück zum Zitat Chalopin, J., Das, S.: Rendezvous of mobile agents without agreement on local orientation. In: Proceedings of the 37th International Conference on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 6199, pp. 515–526 (2010) Chalopin, J., Das, S.: Rendezvous of mobile agents without agreement on local orientation. In: Proceedings of the 37th International Conference on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 6199, pp. 515–526 (2010)
6.
Zurück zum Zitat Cord-Landwehr, A., Degener, B., Fischer, M., Hüllmann, M., Kempkes, B., Klaas, A., Kling, P., Kurras, S., Märtens, M., Der Heide, F.M.A., Raupach, C., Swierkot, K., Warner, D., Weddemann, C., Wonisch, D.: A new approach for analyzing convergence algorithms for mobile robots. In: Proceedings of the 38th International Conference on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 6756, pp. 650–661 (2011) Cord-Landwehr, A., Degener, B., Fischer, M., Hüllmann, M., Kempkes, B., Klaas, A., Kling, P., Kurras, S., Märtens, M., Der Heide, F.M.A., Raupach, C., Swierkot, K., Warner, D., Weddemann, C., Wonisch, D.: A new approach for analyzing convergence algorithms for mobile robots. In: Proceedings of the 38th International Conference on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 6756, pp. 650–661 (2011)
7.
Zurück zum Zitat Czyzowicz, J., Labourel, A., Pelc, A.: How to meet asynchronously (almost) everywhere. In: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 22–30 (2010) Czyzowicz, J., Labourel, A., Pelc, A.: How to meet asynchronously (almost) everywhere. In: Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 22–30 (2010)
8.
Zurück zum Zitat D’Angelo, G., Di Stefano, G., Klasing, R., Navarra, A.: Gathering of robots on anonymous grids without multiplicity detection. In: Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 7355, pp. 327–338 (2012) D’Angelo, G., Di Stefano, G., Klasing, R., Navarra, A.: Gathering of robots on anonymous grids without multiplicity detection. In: Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 7355, pp. 327–338 (2012)
9.
Zurück zum Zitat D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering of six robots on anonymous symmetric rings. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 6796, pp. 174–185 (2011) D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering of six robots on anonymous symmetric rings. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 6796, pp. 174–185 (2011)
10.
Zurück zum Zitat D’Angelo, G., Di Stefano, G., Navarra, A.: How to gather asynchronous oblivious robots on anonymous rings. In: Proceedings of the 26th International Symposium on Distributed Computing (DISC), Lecture Notes in Computer Science, vol. 7611, pp. 330–344 (2012) D’Angelo, G., Di Stefano, G., Navarra, A.: How to gather asynchronous oblivious robots on anonymous rings. In: Proceedings of the 26th International Symposium on Distributed Computing (DISC), Lecture Notes in Computer Science, vol. 7611, pp. 330–344 (2012)
11.
Zurück zum Zitat D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering asynchronous and oblivious robots on basic graph topologies under the look–compute–move model. In: S. Alpern, R. Fokkink, L. Gasieniec, R. Lindelauf, V. Subrahmanian (eds.) Search Theory: A Game Theoretic Perspective, pp. 197–222. Springer, Berlin (2013) D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering asynchronous and oblivious robots on basic graph topologies under the look–compute–move model. In: S. Alpern, R. Fokkink, L. Gasieniec, R. Lindelauf, V. Subrahmanian (eds.) Search Theory: A Game Theoretic Perspective, pp. 197–222. Springer, Berlin (2013)
12.
Zurück zum Zitat D’Angelo, G., Di Stefano, G., Navarra, A., Nisse, N., Suchan, K.: A unified approach for different tasks on rings in robot-based computing systems. In: Proceedings of the 15th IEEE IPDPS Workshop on Advances in Parallel and Distributed Computational Models (APDCM), pp. 667–676 (2013) D’Angelo, G., Di Stefano, G., Navarra, A., Nisse, N., Suchan, K.: A unified approach for different tasks on rings in robot-based computing systems. In: Proceedings of the 15th IEEE IPDPS Workshop on Advances in Parallel and Distributed Computational Models (APDCM), pp. 667–676 (2013)
13.
Zurück zum Zitat 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. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 139–148 (2011) 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. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 139–148 (2011)
14.
15.
Zurück zum Zitat Di Stefano, G., Navarra, A.: Optimal gathering of oblivious robots in anonymous graphs. In: Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 8179, pp. 213–224 (2013) Di Stefano, G., Navarra, A.: Optimal gathering of oblivious robots in anonymous graphs. In: Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 8179, pp. 213–224 (2013)
16.
Zurück zum Zitat Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Remembering without memory: tree exploration by asynchronous oblivious robots. Theor. Comput. Sci. 411(14–15), 1583–1598 (2010)CrossRefMATHMathSciNet Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Remembering without memory: tree exploration by asynchronous oblivious robots. Theor. Comput. Sci. 411(14–15), 1583–1598 (2010)CrossRefMATHMathSciNet
17.
Zurück zum Zitat Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Computing without communicating: ring exploration by asynchronous oblivious robots. Algorithmica 65(3), 562–583 (2013)CrossRefMATHMathSciNet Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Computing without communicating: ring exploration by asynchronous oblivious robots. Algorithmica 65(3), 562–583 (2013)CrossRefMATHMathSciNet
18.
Zurück zum Zitat Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337, 147–168 (2005) Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337, 147–168 (2005)
19.
Zurück zum Zitat Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Randomized gathering of mobile robots with local-multiplicity detection. In: Proceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Lecture Notes in Computer Science, vol. 5873, pp. 384–398 (2009) Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Randomized gathering of mobile robots with local-multiplicity detection. In: Proceedings of the 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Lecture Notes in Computer Science, vol. 5873, pp. 384–398 (2009)
20.
Zurück zum Zitat Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Mobile robots gathering algorithm with local weak multiplicity in rings. In: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 6058, pp. 101–113 (2010) Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Mobile robots gathering algorithm with local weak multiplicity in rings. In: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 6058, pp. 101–113 (2010)
21.
Zurück zum Zitat Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Asynchronous mobile robot gathering from symmetric configurations. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 6796, pp. 150–161 (2011) Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Asynchronous mobile robot gathering from symmetric configurations. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lecture Notes in Computer Science, vol. 6796, pp. 150–161 (2011)
22.
Zurück zum Zitat Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Gathering an even number of robots in an odd ring without global multiplicity detection. In: Proceedings of 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS, vol. 7464, pp. 542–553 (2012) Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Gathering an even number of robots in an odd ring without global multiplicity detection. In: Proceedings of 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS, vol. 7464, pp. 542–553 (2012)
23.
Zurück zum Zitat 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)CrossRefMATHMathSciNet 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)CrossRefMATHMathSciNet
24.
Zurück zum Zitat Klasing, R., Markou, E., Pelc, A.: Gathering asynchronous oblivious mobile robots in a ring. Theor. Comput. Sci. 390, 27–39 (2008)CrossRefMATHMathSciNet Klasing, R., Markou, E., Pelc, A.: Gathering asynchronous oblivious mobile robots in a ring. Theor. Comput. Sci. 390, 27–39 (2008)CrossRefMATHMathSciNet
25.
Zurück zum Zitat Koren, M.: Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej. Technologie Informacyjne 18, 325–331 (2010) Koren, M.: Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydzialu ETI Politechniki Gdanskiej. Technologie Informacyjne 18, 325–331 (2010)
26.
Zurück zum Zitat Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)CrossRefMATHMathSciNet Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)CrossRefMATHMathSciNet
27.
Zurück zum Zitat Yamashita, M., Souissi, S., Défago, X.: Gathering two stateless mobile robots using very inaccurate compasses in finite time. In: Proceedings of the 1st International Conference on Robot Communication and Coordination (RoboComm), pp. 48:1–48:4 (2007) Yamashita, M., Souissi, S., Défago, X.: Gathering two stateless mobile robots using very inaccurate compasses in finite time. In: Proceedings of the 1st International Conference on Robot Communication and Coordination (RoboComm), pp. 48:1–48:4 (2007)
Metadaten
Titel
Gathering on rings under the Look–Compute–Move model
verfasst von
Gianlorenzo D’Angelo
Gabriele Di Stefano
Alfredo Navarra
Publikationsdatum
01.08.2014
Verlag
Springer Berlin Heidelberg
Erschienen in
Distributed Computing / Ausgabe 4/2014
Print ISSN: 0178-2770
Elektronische ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-014-0212-9