Search Results

Documents authored by Pattanayak, Debasish

Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.56
Brief Announcement: Universal Dancing by Luminous Robots Under Sequential Schedulers

Authors: Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, and Nicola Santoro

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
The Dancing problem requires a swarm of n autonomous mobile robots to form a sequence of patterns, aka perform a choreography. Existing work has proven that some crucial restrictions on choreographies and initial configurations (e.g., on repetitions of patterns, periodicity, symmetries, contractions/expansions) must hold so that the Dancing problem can be solved under certain robot models. Here, we prove that these necessary constraints can be dropped by considering the LUMI model (i.e., where robots are endowed with a light whose color can be chosen from a constant-size palette) under the quite unexplored sequential scheduler. We formalize the class of Universal Dancing problems which require a swarm of n robots starting from any initial configuration to perform a (periodic or finite) sequence of arbitrary patterns, only provided that each pattern consists of n vertices (including multiplicities). However, we prove that, to be solvable under LUMI, the length of the feasible choreographies is bounded by the compositions of n into the number of colors available to the robots. We provide an algorithm solving the Universal Dancing problem by exploiting the peculiar capability of sequential robots to implement a distributed counter mechanism. Even assuming non-rigid movements, our algorithm ensures spatial homogeneity of the performed choreography.
Cite as

Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, and Nicola Santoro. Brief Announcement: Universal Dancing by Luminous Robots Under Sequential Schedulers. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 56:1-56:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{feletti_et_al:LIPIcs.DISC.2025.56,
  author =	{Feletti, Caterina and Flocchini, Paola and Pattanayak, Debasish and Prencipe, Giuseppe and Santoro, Nicola},
  title =	{{Brief Announcement: Universal Dancing by Luminous Robots Under Sequential Schedulers}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{56:1--56:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.56},
  URN =		{urn:nbn:de:0030-drops-248724},
  doi =		{10.4230/LIPIcs.DISC.2025.56},
  annote =	{Keywords: Luminous Robots, Sequence of Patterns, Pattern Formation, Sequential Scheduler}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.63
Brief Announcement: Optimal Dispersion Under Asynchrony

Authors: Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study the dispersion problem in anonymous port-labeled graphs: k ≤ n mobile agents, each with a unique ID and initially located arbitrarily on the nodes of an n-node graph with maximum degree Δ, must autonomously relocate so that no node hosts more than one agent. Dispersion serves as a fundamental task in the distributed computing of mobile agents, and its complexity stems from key challenges in local coordination under anonymity and limited memory. The goal is to minimize both the time to achieve dispersion and the memory required per agent. It is known that any algorithm requires Ω(k) time in the worst case, and Ω(log k) bits of memory per agent. A recent result [Kshemkalyani et al., 2025] gives an optimal O(k)-time algorithm in the synchronous setting and an O(k log k)-time algorithm in the asynchronous setting, both using O(log(k+Δ)) bits. We close the complexity gap in the asynchronous setting by presenting the first dispersion algorithm that runs in optimal O(k) time using O(log(k+Δ)) bits of memory per agent. Our solution relies on a novel technique for constructing a port-one tree in anonymous graphs, which may be of independent interest.
Cite as

Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma. Brief Announcement: Optimal Dispersion Under Asynchrony. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 63:1-63:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pattanayak_et_al:LIPIcs.DISC.2025.63,
  author =	{Pattanayak, Debasish and Kshemkalyani, Ajay D. and Kumar, Manish and Molla, Anisur Rahaman and Sharma, Gokarna},
  title =	{{Brief Announcement: Optimal Dispersion Under Asynchrony}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{63:1--63:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.63},
  URN =		{urn:nbn:de:0030-drops-248795},
  doi =		{10.4230/LIPIcs.DISC.2025.63},
  annote =	{Keywords: Distributed algorithms, mobile agents, local communication, dispersion, asynchrony, port-one tree, time and memory complexity}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.46
Brief Announcement: Optimal Uniform Circle Formation by Asynchronous Luminous Robots

Authors: Caterina Feletti, Debasish Pattanayak, and Gokarna Sharma

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
We study the Uniform Circle Formation (UCF) problem for a swarm of n autonomous mobile robots operating in Look-Compute-Move (LCM) cycles on the Euclidean plane. We assume our robots are luminous, i.e. equipped with a persistent light that can assume a color chosen from a fixed palette, and opaque, i.e. not able to see beyond a collinear robot. Robots are said to collide if they share positions or their paths intersect within concurrent LCM cycles. To solve UCF, a swarm of n robots must autonomously arrange themselves so that each robot occupies a vertex of the same regular n-gon not fixed in advance. In terms of efficiency, the goal is to design an algorithm that optimizes (or provides a tradeoff between) two fundamental performance metrics: (i) the execution time and (ii) the size of the color palette. In this paper, we develop a deterministic algorithm solving UCF avoiding collisions in O(1)-time with O(1) colors under the asynchronous scheduler, which is asymptotically optimal with respect to both time and number of colors used, the first such result. Furthermore, the algorithm proposed here minimizes for the first time what we call the computational SEC, i.e. the smallest circular area where robots operate throughout the whole algorithm.
Cite as

Caterina Feletti, Debasish Pattanayak, and Gokarna Sharma. Brief Announcement: Optimal Uniform Circle Formation by Asynchronous Luminous Robots. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 46:1-46:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{feletti_et_al:LIPIcs.DISC.2024.46,
  author =	{Feletti, Caterina and Pattanayak, Debasish and Sharma, Gokarna},
  title =	{{Brief Announcement: Optimal Uniform Circle Formation by Asynchronous Luminous Robots}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{46:1--46:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.46},
  URN =		{urn:nbn:de:0030-drops-212748},
  doi =		{10.4230/LIPIcs.DISC.2024.46},
  annote =	{Keywords: Uniform Circle Formation, Robots with Lights, Autonomous Robots, Rank Encoding, Time and Color Complexities, Computational SEC}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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