Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Distributed Computing
Published in: Distributed Computing 5/2020

06-08-2019

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

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

Published in: Distributed Computing | Issue 5/2020

Log in

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

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.
previous article Confidential gossip
next article Preserving stabilization while practically bounding state space using incorruptible partially synchronized clocks

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!

inform now

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!

inform now

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!

inform now
Appendix
Available only for authorised users
Footnotes
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 }\).
 
Literature
1.
Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56–82 (2006)MathSciNetCrossRef
2.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Dieudonné, Y., Petit, F.: Self-stabilizing gathering with strong multiplicity detection. Theor. Comput. Sci. 428, 47–57 (2012)MathSciNetCrossRef
18.
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.
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.
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.
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.
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1996)MATH
24.
25.
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.
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.
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.
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.
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.
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)MathSciNetCrossRef
Metadata
Title
Self-stabilizing gathering of mobile robots under crash or Byzantine faults
Authors
Xavier Défago
Maria Potop-Butucaru
Philippe Raipin-Parvédy
Publication date
06-08-2019
Publisher
Springer Berlin Heidelberg
Published in
Distributed Computing / Issue 5/2020
Print ISSN: 0178-2770
Electronic ISSN: 1432-0452
DOI
https://doi.org/10.1007/s00446-019-00359-x

Premium Partner

    Image Credits