Arbitrary Pattern Formation in Presence of Crash Faults on Grid - Research Insights
Explore the fascinating world of arbitrary pattern formations in the presence of crash faults on a grid, as presented by Pritam Goswami from Jadavpur University. Discover insights on autonomous robots and the challenges posed by faults in achieving exact pattern formations. Delve into open questions regarding robot behaviors under various constraints such as obliviousness, silence, and synchronicity.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Arbitrary Pattern Formation in Presence of Crash Fault on Grid Pritam Goswami Department of Mathematics, Jadavpur University Presenting at Young Researcher s Forum, Indo-Slovenia Pre-conference School, Caldam,2024 IIT Bhilai
Arbitrary Pattern Formation (APF) on Grid Introduced by Bose et al. [1] Autonomous Anonymous Homogeneous Identical Oblivious Silent Full Visibility (x2,y2) (x3,y3) (x4,y4) (x5,y5) (x7,y7) (x6,y6) (x1,y1) [1] : Bose K., Adhikary R., Kundu M.K., Sau B.: Arbitrary pattern formation on infinite grid by asynchronous oblivious robots. In: Theor. Comput. Sci., vol. 815, pp. 213 227, 2020. URL http://dx.doi.org/10.1016/j.tcs.2020.02.016.
Robot with faults Fault Byzantine Crash
APF on Grid with Crash Fault (x2,y2) (x3,y3) (x4,y4) (x5,y5) (x7,y7) (x6,y6) (x1,y1)
Some Observations and Result 1. Byzantine fault: Exact Pattern Formation not possible 2. 2 or more Crash faults: Exact pattern Formation not possible Impossible to solve : For oblivious and silent robots under semi-synchronous scheduler. Proof Idea: detection of crash is impossible Solved : For Robots having communication using finite bits +fully synchronous scheduler
Open Question Oblivious & Silent + Semi-synchronous Oblivious & Silent + Fully synchronous Finite memory + Semi-synchronous Finite memory + Fully synchronous Communication (finite Bit) + Fully synchronous < < < P. Flocchini, N. Santoro, and K. Wada. On memory, communication, and synchronous schedulers when moving and computing. In Proc. 23rd Int. Conference on Principles of Distributed Systems (OPODIS), pages 25:1 25:17, 2019.
