Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots

Molla, Anisur Rahaman; Mondal, Kaushik; Moses Jr., William K.

Abstract

Over the years, much research involving mobile computational entities has been performed. From modeling actual microscopic (and smaller) robots, to modeling software processes on a network, many important problems have been studied in this context. Gathering is one such fundamental problem in this area. The problem of gathering k robots, initially arbitrarily placed on the nodes of an n-node graph, asks that these robots coordinate and communicate in a local manner, as opposed to global, to move around the graph, find each other, and settle down on a single node as fast as possible. A more difficult problem to solve is gathering with detection, where once the robots gather, they must subsequently realize that gathering has occurred and then terminate. In this paper, we propose a deterministic approach to solve gathering with detection for any arbitrary connected graph that is faster than existing deterministic solutions for even just gathering (without the requirement of detection) for arbitrary graphs. In contrast to earlier work on gathering, it leverages the fact that there are more robots present in the system to achieve gathering with detection faster than those previous papers that focused on just gathering. The state of the art solution for deterministic gathering [Ta-Shma and Zwick, TALG, 2014] takes O˜(n 5 log ℓ) rounds, where ℓ is the smallest label among robots and O˜ hides a polylog factor. We design a deterministic algorithm for gathering with detection with the following trade-offs depending on how many robots are present: (i) when k ≥ ⌊n/2⌋ + 1, the algorithm takes O(n 3 ) rounds, (ii) when k ≥ ⌊n/3⌋+1, the algorithm takes O(n 4 log n) rounds, and (iii) otherwise, the algorithm takes O˜(n 5 ) rounds. The algorithm is not required to know k, but only n

Citation

Molla, A. R., Mondal, K., & Moses Jr., W. K. (2023, May). Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots. Presented at 37th IEEE International Parallel & Distributed Processing Symposium, St. Petersburg, Florida, USA

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 37th IEEE International Parallel & Distributed Processing Symposium
• Start Date: May 15, 2023
• End Date: May 19, 2023
• Acceptance Date: Dec 18, 2022
• Online Publication Date: Jul 18, 2023
• Publication Date: 2023
• Deposit Date: Mar 14, 2023
• Publicly Available Date: Jul 28, 2023
• Publisher: Institute of Electrical and Electronics Engineers
• Pages: 47-57
• Series ISSN: 1530-2075
• Book Title: 2023 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
• ISBN: 9798350337679
• DOI: https://doi.org/10.1109/IPDPS54959.2023.00015
• Public URL: https://durham-repository.worktribe.com/output/1135092
• Publisher URL: https://ieeexplore.ieee.org/xpl/conhome/1000530/all-proceedings