Kshemkalyani, Ajay D. ;
Sharma, Gokarna
NearOptimal Dispersion on Arbitrary Anonymous Graphs
Abstract
Given an undirected, anonymous, portlabeled graph of n memoryless nodes, m edges, and degree Δ, we consider the problem of dispersing k ≤ n robots (or tokens) positioned initially arbitrarily on one or more nodes of the graph to exactly k different nodes of the graph, one on each node. The objective is to simultaneously minimize time to achieve dispersion and memory requirement at each robot. If all k robots are positioned initially on a single node, depth first search (DFS) traversal solves this problem in O(min{m,kΔ}) time with Θ(log(k+Δ)) bits at each robot. However, if robots are positioned initially on multiple nodes, the best previously known algorithm solves this problem in O(min{m,kΔ}⋅ log 𝓁) time storing Θ(log(k+Δ)) bits at each robot, where 𝓁 ≤ k/2 is the number of multiplicity nodes in the initial configuration. In this paper, we present a novel multisource DFS traversal algorithm solving this problem in O(min{m,kΔ}) time with Θ(log(k+Δ)) bits at each robot, improving the time bound of the best previously known algorithm by O(log 𝓁) and matching asymptotically the singlesource DFS traversal bounds. This is the first algorithm for dispersion that is optimal in both time and memory in arbitrary anonymous graphs of constant degree, Δ = O(1). Furthermore, the result holds in both synchronous and asynchronous settings.
BibTeX  Entry
@InProceedings{kshemkalyani_et_al:LIPIcs.OPODIS.2021.8,
author = {Kshemkalyani, Ajay D. and Sharma, Gokarna},
title = {{NearOptimal Dispersion on Arbitrary Anonymous Graphs}},
booktitle = {25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
pages = {8:18:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772198},
ISSN = {18688969},
year = {2022},
volume = {217},
editor = {Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15783},
URN = {urn:nbn:de:0030drops157837},
doi = {10.4230/LIPIcs.OPODIS.2021.8},
annote = {Keywords: Distributed algorithms, Multiagent systems, Mobile robots, Local communication, Dispersion, Exploration, Time and memory complexity}
}
28.02.2022
Keywords: 

Distributed algorithms, Multiagent systems, Mobile robots, Local communication, Dispersion, Exploration, Time and memory complexity 
Seminar: 

25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Issue date: 

2022 
Date of publication: 

28.02.2022 