Top

Published in:

2020 | OriginalPaper | Chapter

Efficient Dispersion on an Anonymous Ring in the Presence of Weak Byzantine Robots

Authors : Anisur Rahaman Molla, Kaushik Mondal, William K. Moses Jr.

Published in: Algorithms for Sensor Systems

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

Abstract

The problem of dispersion of mobile robots on a graph asks that n robots initially placed arbitrarily on the nodes of an n-node anonymous graph, autonomously move to reach a final configuration where exactly each node has at most one robot on it. This problem has been relatively well-studied when robots are non-faulty. In this paper, we introduce the notion of Byzantine faults to this problem, i.e., we formalize the problem of dispersion in the presence of up to f Byzantine robots. We then study the problem on a ring while simultaneously optimizing the time complexity of algorithms and the memory requirement per robot. Specifically, we design deterministic algorithms that attempt to match the time lower bound (\(\varOmega (n)\) rounds) and memory lower bound (\(\varOmega (\log n)\) bits per robot).

Our main result is a deterministic algorithm that is both time and memory optimal, i.e., O(n) rounds and \(O(\log n)\) bits of memory required per robot, subject to certain constraints. We subsequently provide results that require less assumptions but are either only time or memory optimal but not both. We also provide a primitive that takes robots initially gathered at a node of the ring and disperses them in a time and memory optimal manner without additional assumptions required .

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

previous chapter Fast Byzantine Gathering with Visibility in Graphs

next chapter Conic Formation in Presence of Faulty Robots

There are mainly two types of faults–one is “crash fault” which means that once a robot crashes, it is dead and will not be active again thereafter; another one is “Byzantine fault” which means that a robot is alive throughout and may behave maliciously. Note that the Byzantine fault subsumes the crash fault.

In the algorithms, we mention a robot resets its sense of direction, i.e., it resets its notion of clockwise and counter-clockwise. That refers to the robot performing this check again and redefining clockwise and counter-clockwise accordingly.

Note that it is not necessary for a robot to know the value of n in order to maintain a counter using \(\log n\) bits of memory given that the robot’s total memory is \(c \log n\) bits of memory, where c is a sufficiently large constant.

Notice that we say that other co-located robots are to follow \(R_1\), instead of just staying put. This is to ensure that all robots initially co-located with \(R_1\) continue to stay with \(R_1\), even if \(R_1\) is a Byzantine robot and moves around during the \(n+1\) rounds.

Possibly some Byzantine robots may also be gathered as well, but the presence of these robots does not cause problems as the subsequent procedure, Rooted-Ring-Dispersion is correct even in the presence of \(n-1\) Byzantine robots.

This could happen at the beginning of the stage, if the two robots are co-located on the same node.

If r terminates prior to the end of round n, it becomes invisible to other robots. Thus, there is the risk of another non-Byzantine robot settling at the same node as r if r terminates early.

Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235–253 (2006)CrossRef

Auger, C., Bouzid, Z., Courtieu, P., Tixeuil, S., Urbain, X.: Certified impossibility results for byzantine-tolerant mobile robots. In: Higashino, T., Katayama, Y., Masuzawa, T., Potop-Butucaru, M., Yamashita, M. (eds.) SSS 2013. LNCS, vol. 8255, pp. 178–190. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03089-0_13CrossRef

Augustine, J., Moses, Jr., W.K.: Dispersion of mobile robots: a study of memory-time trade-offs. CoRR abs/1707.05629 ([v4] 2018 (a preliminary version appeared in ICDCN’18))

Bampas, E., Gasieniec, L., Hanusse, N., Ilcinkas, D., Klasing, R., Kosowski, A.: Euler tour lock-in problem in the rotor-router model: I choose pointers and you choose port numbers. In: DISC, pp. 423–435 (2009)

Barriere, L., Flocchini, P., Mesa-Barrameda, E., Santoro, N.: Uniform scattering of autonomous mobile robots in a grid. In: IPDPS, pp. 1–8 (2009)

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-9MathSciNetCrossRefMATH

Bouchard, S., Dieudonné, Y., Lamani, A.: Byzantine gathering in polynomial time. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, 9–13 July 2018, pp. 147:1–147:15 (2018)

Bouzid, Z., Potop-Butucaru, M.G., Tixeuil, S.: Byzantine-resilient convergence in oblivious robot networks. In: Garg, V., Wattenhofer, R., Kothapalli, K. (eds.) Distributed Computing and Networking. LNCS, vol. 5408, pp. 275–280. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-92295-7_33CrossRef

Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: gathering. SIAM J. Comput. 41(4), 829–879 (2012)MathSciNetCrossRef

10.

Cieliebak, M., Prencipe, G.: Gathering autonomous mobile robots. In: Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pp. 57–72 (2002)

11.

Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. ACM Trans. Algorithms 4(4), 42:1–42:18 (2008)

12.

Cohen, R., Peleg, D.: Robot convergence via center-of-gravity algorithms. In: Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity, (SIROCCO), pp. 79–88 (2004)

13.

Cybenko, G.: Dynamic load balancing for distributed memory multiprocessors. J. Parallel Distrib. Comput. 7(2), 279–301 (1989)CrossRef

14.

Czyzowicz, J., et al.: Search on a line by byzantine robots. arXiv preprint arXiv:1611.08209 (2016)

15.

Das, S.: Mobile agents in distributed computing: network exploration. Bull. EATCS 109, 54–69 (2013)MATH

16.

Das, S., Focardi, R., Luccio, F.L., Markou, E., Squarcina, M.: Gathering of robots in a ring with mobile faults. Theor. Comput. Sci. 764, 42–60 (2019)MathSciNetCrossRef

17.

Daymude, J.J., Hinnenthal, K., Richa, A.W., Scheideler, C.: Computing by programmable particles. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities. LNCS, vol. 11340, pp. 615–681. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7_22CrossRef

18.

Degener, B., Kempkes, B., Langner, T., Meyer auf der Heide, F., Pietrzyk, P., Wattenhofer, R.: A tight runtime bound for synchronous gathering of autonomous robots with limited visibility. In: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 139–148 (2011)

19.

Dereniowski, D., Disser, Y., Kosowski, A., Pajak, D., Uznański, P.: Fast collaborative graph exploration. Inf. Comput. 243, 37–49 (2015)

20.

Dieudonné, Y., Pelc, A., Peleg, D.: Gathering despite mischief. ACM Trans. Algorithms 11(1), 1:1–1:28 (2014)

21.

Elor, Y., Bruckstein, A.M.: Uniform multi-agent deployment on a ring. Theor. Comput. Sci. 412(8–10), 783–795 (2011)MathSciNetCrossRef

22.

Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. 345(2–3), 331–344 (2005)MathSciNetCrossRef

23.

Kshemkalyani, A.D., Ali, F.: Efficient dispersion of mobile robots on graphs. In: ICDCN, pp. 218–227 (2019)

24.

Kshemkalyani, A.D., Molla, A.R., Sharma, G.: Fast dispersion of mobile robots on arbitrary graphs. In: ALGOSENSORS (2019)

25.

Kshemkalyani, A.D., Molla, A.R., Sharma, G.: Dispersion of mobile robots in the global communication model. In: ICDCN (2020)

26.

Kshemkalyani, A.D., Molla, A.R., Sharma, G.: Dispersion of mobile robots on grids. In: WALCOM (2020)

27.

Menc, A., Pajak, D., Uznanski, P.: Time and space optimality of rotor-router graph exploration. Inf. Process. Lett. 127, 17–20 (2017)MathSciNetCrossRef

28.

Miller, A., Pelc, A.: Tradeoffs between cost and information for rendezvous and treasure hunt. J. Parallel Distrib. Comput. 83, 159–167 (2015)CrossRef

29.

Molla, A.R., Moses Jr., W.K.: Dispersion of mobile robots: the power of randomness. In: TAMC, pp. 481–500 (2019)

30.

Potop-Butucaru, M., Raynal, M., Tixeuil, S.: Distributed computing with mobile robots: an introductory survey. In: The 14th International Conference on Network-Based Information Systems (NBiS), pp. 318–324 (2011)

31.

Poudel, P., Sharma, G.: Time-optimal uniform scattering in a grid. In: ICDCN, pp. 228–237 (2019)

32.

Prencipe, G.: Impossibility of gathering by a set of autonomous mobile robots. Theor. Comput. Sci. 384(2–3), 222–231 (2007)MathSciNetCrossRef

33.

Shibata, M., Mega, T., Ooshita, F., Kakugawa, H., Masuzawa, T.: Uniform deployment of mobile agents in asynchronous rings. In: PODC, pp. 415–424 (2016)

34.

Subramanian, R., Scherson, I.D.: An analysis of diffusive load-balancing. In: SPAA, pp. 220–225 (1994)

35.

Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: Formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)MathSciNetCrossRef

Title: Efficient Dispersion on an Anonymous Ring in the Presence of Weak Byzantine Robots
Authors: Anisur Rahaman Molla
Kaushik Mondal
William K. Moses Jr.
Publisher: Springer International Publishing
Book: Algorithms for Sensor Systems
Print ISBN: 978-3-030-62400-2

Electronic ISBN: 978-3-030-62401-9

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-62401-9_11

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner