Skip to main content
Top
Published in: Distributed Computing 3/2019

15-12-2018

The topology of look-compute-move robot wait-free algorithms with hard termination

Authors: Manuel Alcántara, Armando Castañeda, David Flores-Peñaloza, Sergio Rajsbaum

Published in: Distributed Computing | Issue 3/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Look-Compute-Move models for a set of autonomous robots have been thoroughly studied for over two decades. We consider the standard Asynchronous Luminous Robots (ALR) model, where robots are located in a graph G. Each robot, repeatedly Looks at its surroundings and obtains a snapshot containing the vertices of G, where all robots are located; based on this snapshot, each robot Computes a vertex (adjacent to its current position), and then Moves to it. Robots have visible lights, allowing them to communicate more information than only its actual position, and they move asynchronously, meaning that each one runs at its own arbitrary speed. We are also interested in a case which has been barely explored: the robots need not all be present initially, they might appear asynchronously. We call this the Extended Asynchronous Appearing Luminous Robots (EALR) model. A central problem in the mobile robots area is bringing the robots to the same vertex. We study several versions of this problem, where the robots move towards the same (or close to each other) vertices. And we concentrate on the requirement that each robot executes a finite number of Look-Compute-Move cycles, independently of the interleaving of other robot’s cycles, and then stops. Our main result is direct connections between the (ALR and) EALR model and the asynchronous wait-free multiprocess read/write shared memory (WFSM) model. General robot tasks in a graph are also provided, which include several version of gathering. Finally, using the connection between the EALR model and the WFSM model, a combinatorial topology characterization for the solvable robot tasks is presented.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

Footnotes
1
We could have instead assumed that a process can only atomically read individually shared registers because it is known that is possible to implement an atomic Snapshot in a wait-free manner from read and write operations (see for example [36, 37]).
 
2
Note that with this modification it is straightforward to model systems where all robots are initially visible since the beginning of the execution: the light of every robot is initialized merely to a non-negative value, for example, 0.
 
3
In the Strong version of the EARL, we assume that robots are non-oblivious, non-anonymous, non-disoriented, share the same labeling of G and can detect multiplicities.
 
Literature
1.
go back to reference Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)MathSciNetCrossRefMATH Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)MathSciNetCrossRefMATH
2.
go back to reference Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)MathSciNetCrossRefMATH Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)MathSciNetCrossRefMATH
3.
go back to reference Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, San Francisco, CA (2013)MATH Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, San Francisco, CA (2013)MATH
4.
go back to reference Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory, vol. 3(2). Morgan & Claypool, San Rafael (2012)MATH Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory, vol. 3(2). Morgan & Claypool, San Rafael (2012)MATH
5.
go back to reference Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots, LNCS, vol. 1741, pp. 93–102. Springer, Berlin (1999)MATH Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots, LNCS, vol. 1741, pp. 93–102. Springer, Berlin (1999)MATH
6.
go back to reference Asaf, E., Peleg, D.: Distributed models and algorithms for mobile robot systems. In: 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), LNCS, vol. 4362, pp. 70–87. Springer (2007) Asaf, E., Peleg, D.: Distributed models and algorithms for mobile robot systems. In: 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), LNCS, vol. 4362, pp. 70–87. Springer (2007)
7.
go back to reference Das, S., Flocchini, P., Prencipe, G., Santoro, N., Yamashita, M.: Autonomous mobile robots with lights. Theor. Comput. Sci. 609(P1), 171–184 (2016)MathSciNetCrossRefMATH Das, S., Flocchini, P., Prencipe, G., Santoro, N., Yamashita, M.: Autonomous mobile robots with lights. Theor. Comput. Sci. 609(P1), 171–184 (2016)MathSciNetCrossRefMATH
8.
go back to reference D’Emidio, M., Frigioni, D., Navarra, A.: Synchronous robots vs asynchronous lights-enhanced robots on graphs. In: Electronic Notes in Theoretical Computer Science. Proceedings of ICTCS 2015, the 16th Italian Conference on Theoretical Computer Science, vol. 322, pp. 169–180 (2016) D’Emidio, M., Frigioni, D., Navarra, A.: Synchronous robots vs asynchronous lights-enhanced robots on graphs. In: Electronic Notes in Theoretical Computer Science. Proceedings of ICTCS 2015, the 16th Italian Conference on Theoretical Computer Science, vol. 322, pp. 169–180 (2016)
9.
go back to reference Yu, X., Yung, M.: Agent rendezvous: a dynamic symmetry-breaking problem. In: Automata, Languages and Programming, 23rd International Colloquium, ICALP96, Paderborn, Germany, 8–12 July 1996, Proceedings, LNCS, vol. 1099, pp. 610–621. Springer (1996) Yu, X., Yung, M.: Agent rendezvous: a dynamic symmetry-breaking problem. In: Automata, Languages and Programming, 23rd International Colloquium, ICALP96, Paderborn, Germany, 8–12 July 1996, Proceedings, LNCS, vol. 1099, pp. 610–621. Springer (1996)
10.
go back to reference Potop-Butucaru, M., Raynal, M., Tixeuil, S.: Distributed computing with mobile robots: an introductory survey. In: 2011 14th International Conference on Network-Based Information Systems (NBiS), pp. 318–324 (2011) Potop-Butucaru, M., Raynal, M., Tixeuil, S.: Distributed computing with mobile robots: an introductory survey. In: 2011 14th International Conference on Network-Based Information Systems (NBiS), pp. 318–324 (2011)
11.
go back to reference Prencipe, G.: Autonomous mobile robots: a distributed computing perspective. In: 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), LNCS, vol. 8243, pp. 6–21. Springer (2014) Prencipe, G.: Autonomous mobile robots: a distributed computing perspective. In: 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), LNCS, vol. 8243, pp. 6–21. Springer (2014)
12.
go back to reference Prencipe, G.: Impossibility of gathering by a set of autonomous mobile robots. In: Theoretical Computer Science, Structural Information and Communication Complexity (SIROCCO 2005), vol. 384(2), pp. 222–231 (2007) Prencipe, G.: Impossibility of gathering by a set of autonomous mobile robots. In: Theoretical Computer Science, Structural Information and Communication Complexity (SIROCCO 2005), vol. 384(2), pp. 222–231 (2007)
13.
go back to reference Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: gathering. SIAM J. Comput. 41(4), 829–879 (2012)MathSciNetCrossRefMATH Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: gathering. SIAM J. Comput. 41(4), 829–879 (2012)MathSciNetCrossRefMATH
14.
go back to reference Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1), 147–168 (2005)MathSciNetCrossRefMATH Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1), 147–168 (2005)MathSciNetCrossRefMATH
15.
go back to reference Cieliebak, M.: Gathering non-oblivious mobile robots. In: Farach-Colton, M. (ed.) LATIN 2004: Theoretical Informatics, pp. 577–588. Springer, Berlin (2004)CrossRef Cieliebak, M.: Gathering non-oblivious mobile robots. In: Farach-Colton, M. (ed.) LATIN 2004: Theoretical Informatics, pp. 577–588. Springer, Berlin (2004)CrossRef
16.
go back to reference Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34(6), 1516–1528 (2005)MathSciNetCrossRefMATH Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34(6), 1516–1528 (2005)MathSciNetCrossRefMATH
17.
go back to reference Klasing, R., Markou, E., Pelc, A.: Gathering asynchronous oblivious mobile robots in a ring. Theor. Comput. Sci. 390(1), 27–39 (2008)MathSciNetCrossRefMATH Klasing, R., Markou, E., Pelc, A.: Gathering asynchronous oblivious mobile robots in a ring. Theor. Comput. Sci. 390(1), 27–39 (2008)MathSciNetCrossRefMATH
18.
go back to reference Bonnet, F., Potop-Butucaru, M., Tixeuil, S.: Asynchronous gathering in rings with 4 robots. In: Proceedings of Ad-hoc, Mobile, and Wireless Networks: 15th International Conference (ADHOC-NOW), LNCS, vol. 9724, pp. 311–324. Springer (2016) Bonnet, F., Potop-Butucaru, M., Tixeuil, S.: Asynchronous gathering in rings with 4 robots. In: Proceedings of Ad-hoc, Mobile, and Wireless Networks: 15th International Conference (ADHOC-NOW), LNCS, vol. 9724, pp. 311–324. Springer (2016)
19.
go back to reference D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering on rings under the look-compute-move model. Distrib. Comput. 27(4), 255–285 (2014)MathSciNetCrossRefMATH D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering on rings under the look-compute-move model. Distrib. Comput. 27(4), 255–285 (2014)MathSciNetCrossRefMATH
20.
21.
go back to reference Viglietta, G.: Rendezvous of two robots with visible bits. In: 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013, LNCS, vol. 8243, pp. 291–306. Springer (2014) Viglietta, G.: Rendezvous of two robots with visible bits. In: 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, ALGOSENSORS 2013, LNCS, vol. 8243, pp. 291–306. Springer (2014)
22.
go back to reference D’Angelo, G., Di Stefano, G., Klasing, R., Navarra, A.: Gathering of robots on anonymous grids without multiplicity detection. In: Even, G., Halldórsson, M.M. (eds.) Structural Information and Communication Complexity, pp. 327–338. Springer, Berlin (2012)CrossRef D’Angelo, G., Di Stefano, G., Klasing, R., Navarra, A.: Gathering of robots on anonymous grids without multiplicity detection. In: Even, G., Halldórsson, M.M. (eds.) Structural Information and Communication Complexity, pp. 327–338. Springer, Berlin (2012)CrossRef
23.
go back to reference D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering Asynchronous and Oblivious Robots on Basic Graph Topologies Under the Look-Compute-Move Model, pp. 197–222. Springer, New York (2013)MATH D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering Asynchronous and Oblivious Robots on Basic Graph Topologies Under the Look-Compute-Move Model, pp. 197–222. Springer, New York (2013)MATH
24.
go back to reference Izumi, T., Souissi, S., Katayama, Y., Inuzuka, N., Défago, X., Wada, K., Yamashita, M.: The gathering problem for two oblivious robots with unreliable compasses. CoRR, arXiv:1111.1492 (2011) Izumi, T., Souissi, S., Katayama, Y., Inuzuka, N., Défago, X., Wada, K., Yamashita, M.: The gathering problem for two oblivious robots with unreliable compasses. CoRR, arXiv:​1111.​1492 (2011)
25.
26.
go back to reference Bouzid, Z., Das, S., Tixeuil, S.: Gathering of mobile robots tolerating multiple crash faults. In: IEEE 33rd International Conference on Distributed Computing Systems (ICDCS), pp. 337–346. IEEE Computer Society, Washington, DC, USA (2013) Bouzid, Z., Das, S., Tixeuil, S.: Gathering of mobile robots tolerating multiple crash faults. In: IEEE 33rd International Conference on Distributed Computing Systems (ICDCS), pp. 337–346. IEEE Computer Society, Washington, DC, USA (2013)
27.
go back to reference Bramas, Q., Tixeuil, S.: Wait-free gathering without chirality. In: 22nd Structural Information and Communication Complexity (SIROCCO), LNCS, vol. 9439, pp. 313–327. Springer (2015) Bramas, Q., Tixeuil, S.: Wait-free gathering without chirality. In: 22nd Structural Information and Communication Complexity (SIROCCO), LNCS, vol. 9439, pp. 313–327. Springer (2015)
28.
go back to reference Castañeda, A., Rajsbaum, S., Roy, M.: Two convergence problems for robots on graphs. In: 2016 Seventh Latin-American Symposium on Dependable Computing, LADC 2016, Cali, Colombia, October 19–21, 2016, pp. 81–90. IEEE Computer Society (2016) Castañeda, A., Rajsbaum, S., Roy, M.: Two convergence problems for robots on graphs. In: 2016 Seventh Latin-American Symposium on Dependable Computing, LADC 2016, Cali, Colombia, October 19–21, 2016, pp. 81–90. IEEE Computer Society (2016)
29.
30.
go back to reference De Marco, G., Gargano, L., Kranakis, E., Krizanc, D., Pelc, A., Vaccaro, U.: Asynchronous deterministic rendezvous in graphs. Theor. Comput. Sci. 355(3), 315–326 (2006)MathSciNetCrossRefMATH De Marco, G., Gargano, L., Kranakis, E., Krizanc, D., Pelc, A., Vaccaro, U.: Asynchronous deterministic rendezvous in graphs. Theor. Comput. Sci. 355(3), 315–326 (2006)MathSciNetCrossRefMATH
31.
32.
34.
go back to reference Chalopin, J., Dieudonné, Y., Labourel, A., Pelc, A.: Fault-tolerant rendezvous in networks. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Automata, Languages, and Programming, pp. 411–422. Springer, Berlin (2014) Chalopin, J., Dieudonné, Y., Labourel, A., Pelc, A.: Fault-tolerant rendezvous in networks. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Automata, Languages, and Programming, pp. 411–422. Springer, Berlin (2014)
35.
go back to reference Agathangelou, C., Georgiou, C., Mavronicolas, M.: A distributed algorithm for gathering many fat mobile robots in the plane. In: ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22–24, 2013, pp. 250–259 (2013) Agathangelou, C., Georgiou, C., Mavronicolas, M.: A distributed algorithm for gathering many fat mobile robots in the plane. In: ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22–24, 2013, pp. 250–259 (2013)
36.
go back to reference Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics. Wiley, Hoboken (2004)CrossRefMATH Attiya, H., Welch, J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics. Wiley, Hoboken (2004)CrossRefMATH
37.
go back to reference Raynal, M.: Safe, Regular, and Atomic Read/Write Registers, pp. 305–328. Springer, Berlin (2013) Raynal, M.: Safe, Regular, and Atomic Read/Write Registers, pp. 305–328. Springer, Berlin (2013)
38.
go back to reference Bose, K., Adhikary, R., Chaudhuri, S.G., Sau, B.: Crash tolerant gathering on grid by asynchronous oblivious robots. CoRR, arXiv:1709.00877 (2017) Bose, K., Adhikary, R., Chaudhuri, S.G., Sau, B.: Crash tolerant gathering on grid by asynchronous oblivious robots. CoRR, arXiv:​1709.​00877 (2017)
39.
go back to reference Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC), pp. 91–100 (1993) Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing (STOC), pp. 91–100 (1993)
40.
go back to reference Borowsky, E., Gafni, E., Lynch, N., Rajsbaum, S.: The BG distributed simulation algorithm. Distrib. Comput. 14(3), 127–146 (2001)CrossRef Borowsky, E., Gafni, E., Lynch, N., Rajsbaum, S.: The BG distributed simulation algorithm. Distrib. Comput. 14(3), 127–146 (2001)CrossRef
41.
go back to reference Chaudhuri, S.: More choices allow more faults: set consensus problems in totally asynchronous systems. Inf. Comput. 105(1), 132–158 (1993)MathSciNetCrossRefMATH Chaudhuri, S.: More choices allow more faults: set consensus problems in totally asynchronous systems. Inf. Comput. 105(1), 132–158 (1993)MathSciNetCrossRefMATH
44.
go back to reference Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks (extended abstract). In: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing (STOC), pp. 589–598 (1997) Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks (extended abstract). In: Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing (STOC), pp. 589–598 (1997)
Metadata
Title
The topology of look-compute-move robot wait-free algorithms with hard termination
Authors
Manuel Alcántara
Armando Castañeda
David Flores-Peñaloza
Sergio Rajsbaum
Publication date
15-12-2018
Publisher
Springer Berlin Heidelberg
Published in
Distributed Computing / Issue 3/2019
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-018-0345-3

Premium Partner