Abstract
We consider the gathering task by a team of m synchronous mobile robots in a graph of n nodes. Each robot has an identifier (ID) and runs its own deterministic algorithm, i.e., there is no centralized coordinator. We consider a particularly challenging scenario: there are f Byzantine robots in the team that can behave arbitrarily, and even have the ability to change their IDs to any value at any time. There is no way to distinguish these robots from non-faulty robots, other than perhaps observing strange or unexpected behaviour. The goal of the gathering task is to eventually have all non-faulty robots located at the same node in the same round. It is known that no algorithm can solve this task unless there at least \(f+1\) non-faulty robots in the team. In this paper, we design an algorithm that runs in polynomial time with respect to n and m that matches this bound, i.e., it works in a team that has exactly \(f+1\) non-faulty robots. In our model, we have equipped the robots with sensors that enable each robot to see the subgraph (including robots) within some distance H of its current node. We prove that the gathering task is solvable if this visibility range H is at least the radius of the graph, and not solvable if H is any fixed constant.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Barrameda, E.M., Santoro, N., Shi, W., Taleb, N.: Sensor deployment by a robot in an unknown orthogonal region: achieving full coverage. In: 20th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2014, pp. 951–960 (2014). https://doi.org/10.1109/PADSW.2014.7097915
Barrière, L., Flocchini, P., Barrameda, E.M., Santoro, N.: Uniform scattering of autonomous mobile robots in a grid. Int. J. Found. Comput. Sci. 22(3), 679–697 (2011). https://doi.org/10.1142/S0129054111008295
Bhagat, S., Mukhopadhyaya, K., Mukhopadhyaya, S.: Computation under restricted visibility. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing, vol. 11340, pp. 134–183. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7_7
Bouchard, S., Dieudonné, Y., Ducourthial, B.: Byzantine gathering in networks. Distrib. Comput. 29(6), 435–457 (2016). https://doi.org/10.1007/s00446-016-0276-9
Bouchard, S., Dieudonné, Y., Lamani, A.: Byzantine gathering in polynomial time. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, pp. 147:1–147:15 (2018). https://doi.org/10.4230/LIPIcs.ICALP.2018.147
Chalopin, J., Dieudonné, Y., Labourel, A., Pelc, A.: Rendezvous in networks in spite of delay faults. Distrib. Comput. 29(3), 187–205 (2015). https://doi.org/10.1007/s00446-015-0259-2
Chalopin, J., Godard, E., Naudin, A.: Anonymous graph exploration with binoculars. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 107–122. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48653-5_8
Cicerone, S., Stefano, G.D., Navarra, A.: Asynchronous robots on graphs: gathering. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing, vol. 11340, pp. 184–217. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-D7_8
Défago, X., Potop-Butucaru, M., Tixeuil, S.: Fault-tolerant mobile robots. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing, vol. 11340, pp. 234–251. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7_10
Dieudonné, Y., Pelc, A., Peleg, D.: Gathering despite mischief. ACM Trans. Algorithms (TALG) 11(1), 1 (2014)
Fischer, M., Jung, D., Meyer auf der Heide, F.: Gathering anonymous, oblivious robots on a grid. In: Fernández Anta, A., Jurdzinski, T., Mosteiro, M.A., Zhang, Y. (eds.) ALGOSENSORS 2017. LNCS, vol. 10718, pp. 168–181. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72751-6_13
Flocchini, P.: Gathering. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing, vol. 11340, pp. 63–82. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7_4
Flocchini, P., Prencipe, G., Santoro, N. (eds.): Distributed Computing by Mobile Entities. Current Research in Moving and Computing. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7
Hirose, J., Nakamura, J., Ooshita, F., Inoue, M.: Gathering with a strong team in weakly byzantine environments. CoRR abs/2007.08217 (2020). https://arxiv.org/abs/2007.08217
Hsiang, T.-R., Arkin, E.M., Bender, M.A., Fekete, S.P., Mitchell, J.S.B.: Algorithms for rapidly dispersing robot swarms in unknown environments. In: Boissonnat, J.-D., Burdick, J., Goldberg, K., Hutchinson, S. (eds.) Algorithmic Foundations of Robotics V. STAR, vol. 7, pp. 77–93. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-45058-0_6
Ooshita, F., Datta, A.K., Masuzawa, T.: Self-stabilizing rendezvous of synchronous mobile agents in graphs. In: Spirakis, P., Tsigas, P. (eds.) SSS 2017. LNCS, vol. 10616, pp. 18–32. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69084-1_2
Pelc, A.: Deterministic gathering with crash faults. Networks 72(2), 182–199 (2018). https://doi.org/10.1002/net.21810
Pelc, A.: Deterministic rendezvous algorithms. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities, Current Research in Moving and Computing, vol. 11340, pp. 423–454. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7_17
Tsuchida, M., Ooshita, F., Inoue, M.: Byzantine-tolerant gathering of mobile agents in arbitrary networks with authenticated whiteboards. IEICE Trans. 101–D(3), 602–610 (2018). https://doi.org/10.1587/transinf.2017FCP0008
Acknowledgements
The authors acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), Discovery Grant RGPIN–2017–05936.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Miller, A., Saha, U. (2020). Fast Byzantine Gathering with Visibility in Graphs. In: Pinotti, C.M., Navarra, A., Bagchi, A. (eds) Algorithms for Sensor Systems. ALGOSENSORS 2020. Lecture Notes in Computer Science(), vol 12503. Springer, Cham. https://doi.org/10.1007/978-3-030-62401-9_10
Download citation
DOI: https://doi.org/10.1007/978-3-030-62401-9_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-62400-2
Online ISBN: 978-3-030-62401-9
eBook Packages: Computer ScienceComputer Science (R0)