Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Leader Election in Rings with Bounded Multiplicity (Short Paper) Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Self-stabilizing Robots in Highly Dynamic Environments

verfasst von : Marjorie Bournat, Ajoy K. Datta, Swan Dubois

Erschienen in: Stabilization, Safety, and Security of Distributed Systems

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

This paper deals with the classical problem of exploring a ring by a cohort of synchronous robots. We focus on the perpetual version of this problem in which it is required that each node of the ring is visited by a robot infinitely often.
The challenge in this paper is twofold. First, we assume that the robots evolve in a highly dynamic ring, i.e., edges may appear and disappear unpredictably without any recurrence nor periodicity assumption. The only assumption we made is that each node is infinitely often reachable from any other node. Second, we aim at providing a self-stabilizing algorithm to the robots, i.e., the algorithm must guarantee an eventual correct behavior regardless of the initial state and positions of the robots. Our main contribution is to show that this problem is deterministically solvable in this harsh environment by providing a self-stabilizing algorithm for three robots.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Self-stabilizing Byzantine-Tolerant Distributed Replicated State Machine
Nächstes Kapitel Packet Efficient Implementation of the Omega Failure Detector
Literatur
1.
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)MathSciNetCrossRefMATH
2.
Potop-Butucaru, M., Raynal, M., Tixeuil, S.: Distributed computing with mobile robots: an introductory survey. In: International Conference on Network-Based Information Systems (NBiS), pp. 318–324 (2011)
3.
Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(02), 267–285 (2003)MathSciNetCrossRefMATH
4.
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)CrossRef
5.
Dijkstra, E.: Self-stabilizing systems in spite of distributed control. Commun. ACM 17(11), 643–644 (1974)CrossRefMATH
6.
Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)MATH
7.
Tixeuil, S.: Self-stabilizing Algorithms, Chapman & Hall. In: Algorithms and Theory of Computation Handbook, pp. 26.1-26.45. CRC Press, Taylor & Francis Group (2009)
8.
Shannon, C.: Presentation of a maze-solving machine. In: 8th Conference of the Josiah Macy, Jr. Foundation, pp. 173–180 (1951)
9.
Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Computing without communicating: ring exploration by asynchronous oblivious robots. In: Tovar, E., Tsigas, P., Fouchal, H. (eds.) OPODIS 2007. LNCS, vol. 4878, pp. 105–118. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-77096-1_​8 CrossRef
10.
11.
Baldoni, R., Bonnet, F., Milani, A., Raynal, M.: On the solvability of anonymous partial grids exploration by mobile robots. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) OPODIS 2008. LNCS, vol. 5401, pp. 428–445. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-92221-6_​27 CrossRef
12.
Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: How many oblivious robots can explore a line. Inf. Process. Lett. 111(20), 1027–1031 (2011)MathSciNetCrossRefMATH
13.
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)MathSciNetCrossRefMATH
14.
Chalopin, J., Flocchini, P., Mans, B., Santoro, N.: Network exploration by silent and oblivious robots. In: Thilikos, D.M. (ed.) WG 2010. LNCS, vol. 6410, pp. 208–219. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-16926-7_​20 CrossRef
15.
Datta, A., Lamani, A., Larmore, L., Petit, F.: Ring exploration by oblivious agents with local vision. In: IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 347–356 (2013)
16.
Blin, L., Milani, A., Potop-Butucaru, M., Tixeuil, S.: Exclusive perpetual ring exploration without chirality. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 312–327. Springer, Heidelberg (2010). doi:10.​1007/​978-3-642-15763-9_​29 CrossRef
17.
Flocchini, P., Mans, B., Santoro, N.: Exploration of periodically varying graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 534–543. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-10631-6_​55 CrossRef
18.
Ilcinkas, D., Wade, A.M.: On the power of waiting when exploring public transportation systems. In: Fernàndez Anta, A., Lipari, G., Roy, M. (eds.) OPODIS 2011. LNCS, vol. 7109, pp. 451–464. Springer, Heidelberg (2011). doi:10.​1007/​978-3-642-25873-2_​31 CrossRef
19.
Ilcinkas, D., Wade, A.M.: Exploration of the T-interval-connected dynamic graphs: the case of the ring. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol. 8179, pp. 13–23. Springer, Heidelberg (2013). doi:10.​1007/​978-3-319-03578-9_​2 CrossRef
20.
Ilcinkas, D., Klasing, R., Wade, A.M.: Exploration of constantly connected dynamic graphs based on cactuses. In: Halldórsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 250–262. Springer, Heidelberg (2014). doi:10.​1007/​978-3-319-09620-9_​20
21.
Di Luna, G., Dobrev, S., Flocchini, P., Santoro, N.: Live exploration of dynamic rings. In: IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 570–579 (2016)
22.
Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: Symposium on the Theory of Computing (STOC), pp. 513–522 (2010)
23.
Blin, L., Gradinariu Potop-Butucaru, M., Tixeuil, S.: On the self-stabilization of mobile robots in graphs. In: Tovar, E., Tsigas, P., Fouchal, H. (eds.) OPODIS 2007. LNCS, vol. 4878, pp. 301–314. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-77096-1_​22 CrossRef
24.
Klasing, R., Markou, E., Pelc, A.: Gathering asynchronous oblivious mobile robots in a ring. In: Asano, T. (ed.) ISAAC 2006. LNCS, vol. 4288, pp. 744–753. Springer, Heidelberg (2006). doi:10.​1007/​11940128_​74 CrossRef
25.
Dubois, S., Kaaouachi, M.-H., Petit, F.: Enabling minimal dominating set in highly dynamic distributed systems. In: Pelc, A., Schwarzmann, A.A. (eds.) SSS 2015. LNCS, vol. 9212, pp. 51–66. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-21741-3_​4 CrossRef
26.
Bournat, M., Datta, A.K., Dubois, S.: Self-stabilizing robots in highly dynamic environments. Technical report (2016). arXiv:​1609.​06161
Metadaten
Titel
Self-stabilizing Robots in Highly Dynamic Environments
verfasst von
Marjorie Bournat
Ajoy K. Datta
Swan Dubois
Copyright-Jahr
2016
Buch
Stabilization, Safety, and Security of Distributed Systems

Print ISBN: 978-3-319-49258-2

Electronic ISBN: 978-3-319-49259-9

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-49259-9_5

Premium Partner

    Bildnachweise