Self-stabilizing gathering of mobile robots under crash or Byzantine faults
Tóm tắt
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.
Tài liệu tham khảo
Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56–82 (2006)
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)
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)
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)
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.: 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)
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., 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.: Optimal Byzantine-resilient convergence in uni-dimensional robot networks. Theor. Comput. Sci. 411(34–36), 3154–3168 (2010)
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)
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
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)
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)
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., Gradinariu Potop-Butucaru, M., Clément, J., Messika, S., Raipin Parvédy, P.: Fault and Byzantine tolerant self-stabilizing mobile robots gathering—feasibility study. CoRR, https://arxiv.org/abs/1602.05546
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)
Dieudonné, Y., Petit, F.: Self-stabilizing gathering with strong multiplicity detection. Theor. Comput. Sci. 428, 47–57 (2012)
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)
Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)
Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool, San Rafael (2012)
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous mobile robots with limited visibility. Theor. Comput. Sci. 337, 147–168 (2005)
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)
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, San Francisco (1996)
Lynch, N.A., Segala, R., Vaandrager, F.W.: Hybrid I/O automata. Inf. Comput. 185(1), 105–157 (2003)
Megido, N.: Linear-time algorithms for linear programming in \(\mathbb{R}^3\) and related problems. SIAM J. Comput. 12(4), 759–776 (1983)
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)
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.: 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)
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)
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)