Skip to main content
Erschienen in: Distributed Computing 5/2020

06.08.2019

Self-stabilizing gathering of mobile robots under crash or Byzantine faults

verfasst von: Xavier Défago, Maria Potop-Butucaru, Philippe Raipin-Parvédy

Erschienen in: Distributed Computing | Ausgabe 5/2020

Einloggen

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

search-config
loading …

Abstract

Gathering is a fundamental coordination problem in cooperative mobile robotics. In short, given a set of robots with arbitrary initial locations and no initial agreement on a global coordinate system, gathering requires that all robots, following their algorithm, reach the exact same but not predetermined location. Gathering is particularly challenging in networks where robots are oblivious (i.e., stateless) and direct communication is replaced by observations on their respective locations. Interestingly any algorithm that solves gathering with oblivious robots is inherently self-stabilizing if no specific assumption is made on the initial distribution of the robots. In this paper, we significantly extend the studies of deterministic gathering feasibility under different assumptions related to synchrony and faults (crash and Byzantine). Unlike prior work, we consider a larger set of scheduling strategies, such as bounded schedulers. In addition, we extend our study to the feasibility of probabilistic self-stabilizing gathering in both fault-free and fault-prone environments.

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
With two robots, all configurations are symmetrical and may lead to robots endlessly swapping their positions. In contrast, with three or more robots, an algorithm can be made such that, at each step, either the robots remain symmetrical and they eventually reach the same location, or symmetry is broken and this is used to move one robot at a time into the same location.
 
2
A Byzantine robot is a faulty robot that behaves arbitrarily, possibly in a way to deliberately prevent the other robots from gathering in a stable way.
 
3
The rationale for considering a centralized scheduler is that, with communication facilities, the robots can synchronize by running a mutual exclusion algorithm, such as token passing.
 
4
An extended abstract of this work was presented at DISC [16] in 2006, although it has been considerably extended since. Meanwhile, some authors have published very insightful results on the problem [22].
 
5
In the ASync model [27], a robot exhibits a continuous behavior that can be modeled by an hybrid I/O automaton ([24]).
 
6
The current position is exclusively available in local coordinates.
 
7
A robot can change its position only through move operations.
 
8
Our definition of multiplicity is sometimes called “strong multiplicity”, in contrast to a weaker definition where robots are only able to distinguish whether a given location is occupied by one or by several robots [22].
 
9
Note that all impossibility results proven in the SSync model necessarily hold in the ASync model.
 
10
An algorithm is said to be wait-free if it tolerates the crash of up to \(n-1\) robots.
 
11
Chirality is the ability to distinguish an asymmetrical shape from its mirror image or, in this case, to agree on the orientation of clockwise vs. counter-clockwise rotations.
 
12
A cautious algorithm ensures that the position of all correct robots always remains within the area covered by all other correct robots [8, 9]. In other words, a cautious algorithm ensures that the diameter of all correct robot positions never increases. Originally defined in the context of approximate agreement [18], the notion was later adapted to the context of Byzantine gathering.
 
13
Not necessarily restricted to locations already occupied by a robot.
 
14
While one could imagine an algorithm that enforces a zero probability of a robot to move for some predetermined configurations, the claim holds nevertheless because such an algorithm cannot possibly enforce such conditions in bivalent configurations, since they are undistinguishable to the robots. Since the scheduler is centralized, any successful gathering execution must necessarily transit through a bivalent configuration.
 
15
We use the common definition of “with high probability” to mean that the probability goes to 1 as the number of activations/repetitions goes to infinity.
 
16
Note that \(\varOmega \) is not a circle; it is best described as the inner loop of a limaçon of Pascal.
 
17
C.f., definition of castle and tower in Sect. 2.7.
 
18
By construction of the side move, the target of robot r is located within the sector between r and the next robots (anti-)clockwise. So, in that sector, any other independent robot \(r'\) targeting the same castle must necessarily be collinear with r in https://static-content.springer.com/image/art%3A10.1007%2Fs00446-019-00359-x/MediaObjects/446_2019_359_Figcx_HTML.gif and take a straight move only if its distance to the castle is smaller than that of r.
 
19
Situations in which robots form a chain or a cycle result in the creation of fewer castles, which is less favorable to the adversary \({ Adv }\).
 
Literatur
1.
Zurück zum Zitat Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56–82 (2006)MathSciNetCrossRef Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56–82 (2006)MathSciNetCrossRef
2.
Zurück zum Zitat Ando, H., Oasa, Y., Suzuki, I., Yamashita, M.: Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans. Robot. Autom. 15(5), 818–828 (1999)CrossRef Ando, H., Oasa, Y., Suzuki, I., Yamashita, M.: Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans. Robot. Autom. 15(5), 818–828 (1999)CrossRef
3.
Zurück zum Zitat Balabonski, T., Delga, A., Rieg, L., Tixeuil, S., Urbain, X.: Synchronous gathering without multiplicity detection: a certified algorithm. In: Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), LNCS, vol. 10083, pp. 7–19, Lyon, France (November 2016) Balabonski, T., Delga, A., Rieg, L., Tixeuil, S., Urbain, X.: Synchronous gathering without multiplicity detection: a certified algorithm. In: Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), LNCS, vol. 10083, pp. 7–19, Lyon, France (November 2016)
4.
Zurück zum Zitat Bhagat, S., Gan Chaudhuri, S., Mukhopadhyaya, K.: Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement. J. Discrete Algorithms 36, 50–62 (2016)MathSciNetCrossRef Bhagat, S., Gan Chaudhuri, S., Mukhopadhyaya, K.: Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement. J. Discrete Algorithms 36, 50–62 (2016)MathSciNetCrossRef
5.
Zurück zum Zitat Bhagat, S., Mukhopadhyaya, K.: Fault-tolerant gathering of semi-synchronous robots. In: Proceedings of the 18th International Conference on Distributed Computing and Networking (ICDCN), number 6, Hyderabad, India (January 2017) Bhagat, S., Mukhopadhyaya, K.: Fault-tolerant gathering of semi-synchronous robots. In: Proceedings of the 18th International Conference on Distributed Computing and Networking (ICDCN), number 6, Hyderabad, India (January 2017)
6.
Zurück zum Zitat Bhagat, S., Mukhopadhyaya, K.: Optimum gathering of asynchronous robots. In: Proceedings of the 3rd International Conference on Algorithms and Discrete Applied Mathematics (CALDAM), LNCS, vol. 10156, pp. 37–49, Sancoale, Goa, India (February 2017) Bhagat, S., Mukhopadhyaya, K.: Optimum gathering of asynchronous robots. In: Proceedings of the 3rd International Conference on Algorithms and Discrete Applied Mathematics (CALDAM), LNCS, vol. 10156, pp. 37–49, Sancoale, Goa, India (February 2017)
7.
Zurück zum Zitat Bouzid, Z., Das, S., Tixeuil, S.: Gathering of mobile robots tolerating multiple crash faults. In: Proceedings of the 33rd IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 337–346, Philadelphia, PA, USA (July 2013) Bouzid, Z., Das, S., Tixeuil, S.: Gathering of mobile robots tolerating multiple crash faults. In: Proceedings of the 33rd IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 337–346, Philadelphia, PA, USA (July 2013)
8.
Zurück zum Zitat Bouzid, Z., Gradinariu Potop-Butucaru, M., Tixeuil, S.: Byzantine convergence in robot networks: the price of asynchrony. In: Proceedings of the 13th International Conference on Principles of Distributed Systems (OPODIS), LNCS, vol. 5923, pp. 54–70, Nîmes, France (December 2009) Bouzid, Z., Gradinariu Potop-Butucaru, M., Tixeuil, S.: Byzantine convergence in robot networks: the price of asynchrony. In: Proceedings of the 13th International Conference on Principles of Distributed Systems (OPODIS), LNCS, vol. 5923, pp. 54–70, Nîmes, France (December 2009)
9.
Zurück zum Zitat Bouzid, Z., Gradinariu Potop-Butucaru, M., Tixeuil, S.: Optimal Byzantine-resilient convergence in uni-dimensional robot networks. Theor. Comput. Sci. 411(34–36), 3154–3168 (2010)MathSciNetCrossRef Bouzid, Z., Gradinariu Potop-Butucaru, M., Tixeuil, S.: Optimal Byzantine-resilient convergence in uni-dimensional robot networks. Theor. Comput. Sci. 411(34–36), 3154–3168 (2010)MathSciNetCrossRef
10.
Zurück zum Zitat Bramas, Q., Tixeuil, S.: Wait-free gathering without chirality. In: Structural Information and Communication Complexity—22nd International Colloquium (SIROCCO), Post-Proceedings, LNCS, vol. 9439, pp. 313–327. Montserrat, Spain (July 2015) Bramas, Q., Tixeuil, S.: Wait-free gathering without chirality. In: Structural Information and Communication Complexity—22nd International Colloquium (SIROCCO), Post-Proceedings, LNCS, vol. 9439, pp. 313–327. Montserrat, Spain (July 2015)
11.
Zurück zum Zitat Clement, J., Défago, X., Gradinariu Potop-Butucaru, M., Messika, S., Raipin-Parvédy, P.: Fault and Byzantine tolerant self-stabilizing mobile robots gathering. Technical Report \(\langle \)hal-00746087\(\rangle \) (February 2012). https://hal.inria.fr/hal-00746087 Clement, J., Défago, X., Gradinariu Potop-Butucaru, M., Messika, S., Raipin-Parvédy, P.: Fault and Byzantine tolerant self-stabilizing mobile robots gathering. Technical Report \(\langle \)hal-00746087\(\rangle \) (February 2012). https://​hal.​inria.​fr/​hal-00746087
12.
Zurück zum Zitat Cohen, R., Peleg, D.: Convergence of autonomous mobile robots with inaccurate sensors and movements. In: Durand, B., Thomas, W. (eds.) 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS’06), LNCS, vol. 3884, pp. 549–560. Springer, Marseille, France (2006) Cohen, R., Peleg, D.: Convergence of autonomous mobile robots with inaccurate sensors and movements. In: Durand, B., Thomas, W. (eds.) 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS’06), LNCS, vol. 3884, pp. 549–560. Springer, Marseille, France (2006)
13.
Zurück zum Zitat Courtieu, P., Rieg, L., Tixeuil, S., Urbain, X.: Certified universal gathering in \({\mathbb{R}}^2\) for oblivious mobile robots. In: Proceedings of the 30th International Symposium on Distributed Computing (DISC), LNCS, vol. 9888, pp. 187–200, Paris, France (September 2016) Courtieu, P., Rieg, L., Tixeuil, S., Urbain, X.: Certified universal gathering in \({\mathbb{R}}^2\) for oblivious mobile robots. In: Proceedings of the 30th International Symposium on Distributed Computing (DISC), LNCS, vol. 9888, pp. 187–200, Paris, France (September 2016)
14.
Zurück zum Zitat Défago, X., Gardinariu Potop-Butucaru, M., Clément, J., Messika, S., Raipin-Parvédy, P.: Fault and Byzantine tolerant self-stabilizing mobile robots gathering. Research Report IS-RR-2015-003, Japan Adv. Inst. of Science and Tech. (JAIST), Hokuriku, Japan (February 2015) Défago, X., Gardinariu Potop-Butucaru, M., Clément, J., Messika, S., Raipin-Parvédy, P.: Fault and Byzantine tolerant self-stabilizing mobile robots gathering. Research Report IS-RR-2015-003, Japan Adv. Inst. of Science and Tech. (JAIST), Hokuriku, Japan (February 2015)
15.
16.
Zurück zum Zitat Défago, X., Gradinariu Potop-Butucaru, M., Messika, S., Raipin-Parvédy, P.: Fault-tolerant and self-stabilizing mobile robots gathering: feasibility study. In: DISC’06, pp. 46–60 (2006) Défago, X., Gradinariu Potop-Butucaru, M., Messika, S., Raipin-Parvédy, P.: Fault-tolerant and self-stabilizing mobile robots gathering: feasibility study. In: DISC’06, pp. 46–60 (2006)
17.
Zurück zum Zitat Dieudonné, Y., Petit, F.: Self-stabilizing gathering with strong multiplicity detection. Theor. Comput. Sci. 428, 47–57 (2012)MathSciNetCrossRef Dieudonné, Y., Petit, F.: Self-stabilizing gathering with strong multiplicity detection. Theor. Comput. Sci. 428, 47–57 (2012)MathSciNetCrossRef
18.
Zurück zum Zitat Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. J. ACM 33(3), 499–516 (1986)MathSciNetCrossRef Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. J. ACM 33(3), 499–516 (1986)MathSciNetCrossRef
19.
20.
Zurück zum Zitat Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool, San Rafael (2012)MATH Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool, San Rafael (2012)MATH
21.
Zurück zum Zitat Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous mobile robots with limited visibility. Theor. Comput. Sci. 337, 147–168 (2005)CrossRef Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous mobile robots with limited visibility. Theor. Comput. Sci. 337, 147–168 (2005)CrossRef
22.
Zurück zum Zitat Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Feasibility of polynomial-time randomized gathering for oblivious mobile robots. IEEE Trans. Parallel Distrib. Syst. 24(4), 716–723 (2013)CrossRef Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Feasibility of polynomial-time randomized gathering for oblivious mobile robots. IEEE Trans. Parallel Distrib. Syst. 24(4), 716–723 (2013)CrossRef
23.
Zurück zum Zitat Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1996)MATH Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1996)MATH
24.
25.
Zurück zum Zitat Megido, N.: Linear-time algorithms for linear programming in \(\mathbb{R}^3\) and related problems. SIAM J. Comput. 12(4), 759–776 (1983)MathSciNetCrossRef Megido, N.: Linear-time algorithms for linear programming in \(\mathbb{R}^3\) and related problems. SIAM J. Comput. 12(4), 759–776 (1983)MathSciNetCrossRef
26.
Zurück zum Zitat Pattanayak, D., Mondal, K., Ramesh, H., Sarathi Mandal, P.: Fault-tolerant gathering of mobile robots with weak multiplicity detection. In: Proceedings of the 18th International Conference on Distributed Computing and Networking, Hyderabad, India, January 5–7, 2017, p. 7 (2017) Pattanayak, D., Mondal, K., Ramesh, H., Sarathi Mandal, P.: Fault-tolerant gathering of mobile robots with weak multiplicity detection. In: Proceedings of the 18th International Conference on Distributed Computing and Networking, Hyderabad, India, January 5–7, 2017, p. 7 (2017)
27.
Zurück zum Zitat Prencipe, G.: Corda: Distributed coordination of a set of autonomous mobile robots. In: Proceedings of the 4th European Research Seminar on Advances in Distributed Systems (ERSADS’01), pp. 185–190, Bertinoro, Italy (May 2001) Prencipe, G.: Corda: Distributed coordination of a set of autonomous mobile robots. In: Proceedings of the 4th European Research Seminar on Advances in Distributed Systems (ERSADS’01), pp. 185–190, Bertinoro, Italy (May 2001)
28.
Zurück zum Zitat Prencipe, G.: On the feasibility of gathering by autonomous mobile robots. In: Pelc, A., Raynal, M. (eds.) Proceedings of the Structural Information and Communication Complexity, 12th Intl Coll., SIROCCO 2005, LNCS, vol. 3499, pp. 246–261. Springer, Mont Saint-Michel, France (May 2005) Prencipe, G.: On the feasibility of gathering by autonomous mobile robots. In: Pelc, A., Raynal, M. (eds.) Proceedings of the Structural Information and Communication Complexity, 12th Intl Coll., SIROCCO 2005, LNCS, vol. 3499, pp. 246–261. Springer, Mont Saint-Michel, France (May 2005)
29.
Zurück zum Zitat Souissi, S., Défago, X., Yamashita, M.: Using eventually consistent compasses to gather memory-less mobile robots with limited visibility. ACM Trans. Auton. Adapt. Syst. 4(1), 9:1–27 (2009)CrossRef Souissi, S., Défago, X., Yamashita, M.: Using eventually consistent compasses to gather memory-less mobile robots with limited visibility. ACM Trans. Auton. Adapt. Syst. 4(1), 9:1–27 (2009)CrossRef
30.
Zurück zum Zitat Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)MathSciNetCrossRef Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)MathSciNetCrossRef
Metadaten
Titel
Self-stabilizing gathering of mobile robots under crash or Byzantine faults
verfasst von
Xavier Défago
Maria Potop-Butucaru
Philippe Raipin-Parvédy
Publikationsdatum
06.08.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
Distributed Computing / Ausgabe 5/2020
Print ISSN: 0178-2770
Elektronische ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-019-00359-x