Document Open Access Logo

Randomized Byzantine Gathering in Rings

Authors John Augustine , Arnhav Datar , Nischith Shadagopan

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2022.13.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Author Details

John Augustine
  • Indian Institute of Technology Madras, India
Arnhav Datar
  • Indian Institute of Technology Madras, India
  • Carnegie Mellon University, Pittsburgh, PA, USA
Nischith Shadagopan
  • Indian Institute of Technology Madras, India

Funding

  • Augustine, John: Supported by the Cybersecurity Research Centre under the IIT Madras Institute of Eminence scheme.
  • Shadagopan, Nischith: Supported by the Young Research Fellowship 2020, IIT Madras.

Cite As Get BibTex

John Augustine, Arnhav Datar, and Nischith Shadagopan. Randomized Byzantine Gathering in Rings. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.OPODIS.2022.13

Abstract

We study the problem of gathering k anonymous mobile agents on a ring with n nodes. Importantly, f out of the k anonymous agents are Byzantine. The agents operate synchronously and in an autonomous fashion. In each round, each agent can communicate with other agents co-located with it by broadcasting a message. After receiving all the messages, each agent decides to either move to a neighbouring node or stay put. We begin with the k agents placed arbitrarily on the ring, and the task is to gather all the good agents in a single node. The task is made harder by the presence of Byzantine agents, which are controlled by a single Byzantine adversary. Byzantine agents can deviate arbitrarily from the protocol. The Byzantine adversary is computationally unbounded. Additionally, the Byzantine adversary is adaptive in the sense that it can capitalize on information gained over time (including the current round) to choreograph the actions of Byzantine agents. Specifically, the entire state of the system, which includes messages sent by all the agents and any random bits generated by the agents, is known to the Byzantine adversary before all the agents move. Thus the Byzantine adversary can compute the positioning of good agents across the ring and choreograph the movement of Byzantine agents accordingly. Moreover, we consider two settings: standard and visual tracking setting. With visual tracking, agents have the ability to track other agents that are moving along with them. In the standard setting, agents do not have such an ability.
In the standard setting we can achieve gathering in 𝒪(nlog nlog k) rounds with high probability and can handle 𝒪(k/(log k)) number of Byzantine agents. With visual tracking, we can achieve gathering faster in 𝒪(n log n) rounds whp and can handle any constant fraction of the total number of agents being Byzantine.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Self-organization
  • Theory of computation → Self-organization
Keywords
  • Mobile agents and robots

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noa Agmon and David Peleg. Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput., 36(1):56-82, July 2006. URL: https://doi.org/10.1137/050645221.
  2. Steve Alpern, V. J. Baston, and Skander Essegaier. Rendezvous search on a graph. Journal of Applied Probability, 36(1):223-231, 1999. URL: http://www.jstor.org/stable/3215416.
  3. Steve Alpern and Shmuel Gal. The theory of search games and rendezvous, volume 55. Springer Science & Business Media, 2006. Google Scholar
  4. James Aspnes. Lower bounds for distributed coin-flipping and randomized consensus. Journal of the ACM (JACM), 45(3):415-450, 1998. Google Scholar
  5. Michael Ben-Or and Nathan Linial. Collective coin flipping, robust voting schemes and minima of banzhaf values. In 26th Annual Symposium on Foundations of Computer Science (FOCS), pages 408-416. IEEE, 1985. Google Scholar
  6. Sébastien Bouchard, Yoann Dieudonné, and Bertrand Ducourthial. Byzantine gathering in networks. Distrib. Comput., 29(6):435-457, November 2016. URL: https://doi.org/10.1007/s00446-016-0276-9.
  7. Sébastien Bouchard, Yoann Dieudonné, and Anissa Lamani. Byzantine Gathering in Polynomial Time. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 147:1-147:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.147.
  8. Colin Cooper, Robert Elsässer, Hirotaka Ono, and Tomasz Radzik. Coalescing random walks and voting on graphs. In Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, PODC '12, pages 47-56, New York, NY, USA, 2012. Association for Computing Machinery. URL: https://doi.org/10.1145/2332432.2332440.
  9. Gianlorenzo D'angelo, Gabriele Di Stefano, and Alfredo Navarra. Gathering on rings under the look - compute - move model. Distrib. Comput., 27(4):255-285, August 2014. URL: https://doi.org/10.1007/s00446-014-0212-9.
  10. Gianlorenzo D'angelo, Alfredo Navarra, and Nicolas Nisse. A unified approach for gathering and exclusive searching on rings under weak assumptions. Distrib. Comput., 30(1):17-48, February 2017. URL: https://doi.org/10.1007/s00446-016-0274-y.
  11. Shantanu Das et al. Mobile agents in distributed computing: Network exploration. Bulletin of EATCS, 1(109), 2013. Google Scholar
  12. Xavier Défago, Maria Potop-Butucaru, and Philippe Raipin Parvédy. Self-stabilizing gathering of mobile robots under crash or byzantine faults. Distributed Comput., 33(5):393-421, 2020. URL: https://doi.org/10.1007/s00446-019-00359-x.
  13. Yoann Dieudonné, Andrzej Pelc, and David Peleg. Gathering despite mischief. ACM Trans. Algorithms, 11(1), August 2014. URL: https://doi.org/10.1145/2629656.
  14. R. Eguchi, N. Kitamura, and T. Izumi. Fast neighborhood rendezvous. In 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS), pages 168-178, Los Alamitos, CA, USA, December 2020. IEEE Computer Society. URL: https://doi.org/10.1109/ICDCS47774.2020.00030.
  15. Uriel Feige. Noncryptographic selection protocols. In 40th Annual Symposium on Foundations of Computer Science (FOCS), pages 142-152. IEEE, 1999. Google Scholar
  16. Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-11072-7.
  17. Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta. Distributed computing by mobile robots: uniform circle formation. Distributed Comput., 30(6):413-457, 2017. URL: https://doi.org/10.1007/s00446-016-0291-x.
  18. Jion Hirose, Junya Nakamura, Fukuhito Ooshita, and Michiko Inoue. Gathering with a strong team in weakly byzantine environments. In International Conference on Distributed Computing and Networking 2021, ICDCN '21, pages 26-35, New York, NY, USA, 2021. Association for Computing Machinery. URL: https://doi.org/10.1145/3427796.3427799.
  19. Daniel S. Hirschberg and James B Sinclair. Decentralized extrema-finding in circular configurations of processors. Communications of the ACM, 23(11):627-628, 1980. Google Scholar
  20. Zool Hilmi Ismail and Nohaidda Sariff. A survey and analysis of cooperative multi-agent robot systems: Challenges and directions. In Efren Gorrostieta Hurtado, editor, Applications of Mobile Robots, chapter 1. IntechOpen, Rijeka, 2019. URL: https://doi.org/10.5772/intechopen.79337.
  21. Taisuke Izumi, Tomoko Izumi, Sayaka Kamei, and Fukuhito Ooshita. Feasibility of polynomial-time randomized gathering for oblivious mobile robots. IEEE Transactions on Parallel and Distributed Systems, 24(4):716-723, 2013. URL: https://doi.org/10.1109/TPDS.2012.212.
  22. Tomoko Izumi, Taisuke Izumi, Sayaka Kamei, and Fukuhito Ooshita. Mobile robots gathering algorithm with local weak multiplicity in rings. In Proceedings of the 17th International Conference on Structural Information and Communication Complexity, SIROCCO'10, pages 101-113, Berlin, Heidelberg, 2010. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-13284-1_9.
  23. Gangshan Jing, Yuanshi Zheng, and Long Wang. Consensus of multiagent systems with distance-dependent communication networks. IEEE Transactions on Neural Networks and Learning Systems, PP, August 2016. URL: https://doi.org/10.1109/TNNLS.2016.2598355.
  24. Ralf Klasing, Adrian Kosowski, and Alfredo Navarra. Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring. Theoretical Computer Science, 411(34):3235-3246, 2010. URL: https://doi.org/10.1016/j.tcs.2010.05.020.
  25. Evangelos Kranakis and Danny Krizanc. Mobile Agents and Exploration, pages 1338-1341. Springer New York, New York, NY, 2016. URL: https://doi.org/10.1007/978-1-4939-2864-4_242.
  26. Silvio Micali and Tal Rabin. Collective coin tossing without assumptions nor broadcasting. In Conference on the Theory and Application of Cryptography, pages 253-266. Springer, 1990. Google Scholar
  27. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Cambridge University Press, USA, 2nd edition, 2017. Google Scholar
  28. Fukuhito Ooshita, Shinji Kawai, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Randomized gathering of mobile agents in anonymous unidirectional ring networks. IEEE Trans. Parallel Distributed Syst., 25(5):1289-1296, 2014. URL: https://doi.org/10.1109/TPDS.2013.259.
  29. Michael Saks. A robust noncryptographic protocol for collective coin flipping. SIAM Journal on Discrete Mathematics, 2(2):240-244, 1989. Google Scholar
  30. Masahiro Shibata, Toshiya Mega, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Uniform deployment of mobile agents in asynchronous rings. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC '16, pages 415-424, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2933057.2933093.
  31. Yuichi Sudo, Daisuke Baba, Junya Nakamura, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. An agent exploration in unknown undirected graphs with whiteboards. In Proceedings of the Third International Workshop on Reliability, Availability, and Security, WRAS '10, New York, NY, USA, 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1953563.1953570.
  32. Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28(4):1347-1363, 1999. URL: https://doi.org/10.1137/S009753979628292X.
  33. Masashi Tsuchida, Fukuhito Ooshita, and Michiko Inoue. Byzantine gathering in networks with authenticated whiteboards. In Sheung-Hung Poon, Md. Saidur Rahman, and Hsu-Chun Yen, editors, WALCOM: Algorithms and Computation, pages 106-118, Cham, 2017. Springer International Publishing. Google Scholar
  34. Xiaoping Yun, Gokhan Alptekin, and Okay Albayrak. Line and circle formation of distributed physical mobile robots. J. Field Robotics, 14(2):63-76, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact