Search Results

Documents authored by Das, Shantanu

Document
DOI: 10.4230/LIPIcs.OPODIS.2020.24
Broadcasting with Mobile Agents in Dynamic Networks

Authors: Shantanu Das, Nikos Giachoudis, Flaminia L. Luccio, and Euripides Markou

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
We study the standard communication problem of broadcast for mobile agents moving in a network. The agents move autonomously in the network and can communicate with other agents only when they meet at a node. In this model, broadcast is a communication primitive for information transfer from one agent, the source, to all other agents. Previous studies of this problem were restricted to static networks while, in this paper, we consider the problem in dynamic networks modelled as an evolving graph. The dynamicity of the graph is unknown to the agents; in each round an adversary selects which edges of the graph are available, and an agent can choose to traverse one of the available edges adjacent to its current location. The only restriction on the adversary is that the subgraph of available edges in each round must span all nodes; in other words the evolving graph is constantly connected. The agents have global visibility allowing them to see the location of other agents in the graph and move accordingly. Depending on the topology of the underlying graph, we determine how many agents are necessary and sufficient to solve the broadcast problem in dynamic networks. While two agents plus the source are sufficient for ring networks, much larger teams of agents are necessary for denser graphs such as grid graphs and hypercubes, and finally for complete graphs of n nodes at least n-2 agents plus the source are necessary and sufficient. We show lower bounds on the number of agents and provide some algorithms for solving broadcast using the minimum number of agents, for various topologies.
Cite as

Shantanu Das, Nikos Giachoudis, Flaminia L. Luccio, and Euripides Markou. Broadcasting with Mobile Agents in Dynamic Networks. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.OPODIS.2020.24,
  author =	{Das, Shantanu and Giachoudis, Nikos and Luccio, Flaminia L. and Markou, Euripides},
  title =	{{Broadcasting with Mobile Agents in Dynamic Networks}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.24},
  URN =		{urn:nbn:de:0030-drops-135095},
  doi =		{10.4230/LIPIcs.OPODIS.2020.24},
  annote =	{Keywords: Distributed Algorithm, Dynamic Networks, Mobile Agents, Broadcast, Constantly Connected, Global visibility}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.24
Oblivious Permutations on the Plane

Authors: Shantanu Das, Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
We consider a distributed system of n identical mobile robots operating in the two dimensional Euclidian plane. As in the previous studies, we consider the robots to be anonymous, oblivious, dis-oriented, and without any communication capabilities, operating based on the Look-Compute-Move model where the next location of a robot depends only on its view of the current configuration. Even in this seemingly weak model, most formation problems which require constructing specific configurations, can be solved quite easily when the robots are fully synchronized with each other. In this paper we introduce and study a new class of problems which, unlike the studied formation problems, cannot always be solved even in the fully synchronous model with atomic and rigid moves. This class of problems requires the robots to permute their locations in the plane. In particular, we are interested in implementing two special types of permutations - permutations without any fixed points and permutations of order n. The former (called Move-All) requires each robot to visit at least two of the initial locations, while the latter (called Visit-All) requires every robot to visit each of the initial locations in a periodic manner. We provide a characterization of the solvability of these problems, showing the main challenges in solving this class of problems for mobile robots. We also provide algorithms for the feasible cases, in particular distinguishing between one-step algorithms (where each configuration must be a permutation of the original configuration) and multi-step algorithms (which allow intermediate configurations). These results open a new research direction in mobile distributed robotics which has not been investigated before.
Cite as

Shantanu Das, Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita. Oblivious Permutations on the Plane. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.OPODIS.2019.24,
  author =	{Das, Shantanu and Di Luna, Giuseppe A. and Flocchini, Paola and Santoro, Nicola and Viglietta, Giovanni and Yamashita, Masafumi},
  title =	{{Oblivious Permutations on the Plane}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.24},
  URN =		{urn:nbn:de:0030-drops-118103},
  doi =		{10.4230/LIPIcs.OPODIS.2019.24},
  annote =	{Keywords: Distributed Algorithms, Mobile Robots, Fully synchronous, Oblivious, Permutations, Chirality, Sequence of configurations}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.ICALP.2018.165
Brief Announcement: Energy Constrained Depth First Search

Authors: Shantanu Das, Dariusz Dereniowski, and Przemyslaw Uznanski

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
Depth first search is a natural algorithmic technique for constructing a closed route that visits all vertices of a graph. The length of such route equals, in an edge-weighted tree, twice the total weight of all edges of the tree and this is asymptotically optimal over all exploration strategies. This paper considers a variant of such search strategies where the length of each route is bounded by a positive integer B (e.g. due to limited energy resources of the searcher). The objective is to cover all the edges of a tree T using the minimum number of routes, each starting and ending at the root and each being of length at most B. To this end, we analyze the following natural greedy tree traversal process that is based on decomposing a depth first search traversal into a sequence of limited length routes. Given any arbitrary depth first search traversal R of the tree T, we cover R with routes R_1,...,R_l, each of length at most B such that: R_i starts at the root, reaches directly the farthest point of R visited by R_{i-1}, then R_i continues along the path R as far as possible, and finally R_i returns to the root. We call the above algorithm piecemeal-DFS and we prove that it achieves the asymptotically minimal number of routes l, regardless of the choice of R. Our analysis also shows that the total length of the traversal (and thus the traversal time) of piecemeal-DFS is asymptotically minimum over all energy-constrained exploration strategies. The fact that R can be chosen arbitrarily means that the exploration strategy can be constructed in an online fashion when the input tree T is not known in advance. Each route R_i can be constructed without any knowledge of the yet unvisited part of T. Surprisingly, our results show that depth first search is efficient for energy constrained exploration of trees, even though it is known that the same does not hold for energy constrained exploration of arbitrary graphs.
Cite as

Shantanu Das, Dariusz Dereniowski, and Przemyslaw Uznanski. Brief Announcement: Energy Constrained Depth First Search. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 165:1-165:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.ICALP.2018.165,
  author =	{Das, Shantanu and Dereniowski, Dariusz and Uznanski, Przemyslaw},
  title =	{{Brief Announcement: Energy Constrained Depth First Search}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{165:1--165:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.165},
  URN =		{urn:nbn:de:0030-drops-91693},
  doi =		{10.4230/LIPIcs.ICALP.2018.165},
  annote =	{Keywords: DFS traversal, distributed algorithm, graph exploration, piecemeal exploration, online exploration}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.10
Energy-Efficient Delivery by Heterogeneous Mobile Agents

Authors: Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld, and Paolo Penna

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We consider the problem of delivering m messages between specified source-target pairs in an undirected graph, by k mobile agents initially located at distinct nodes of the graph. Each edge has a designated length and each agent consumes energy proportional to the distance it travels in the graph. We are interested in optimizing the total energy consumption for the team of agents. Unlike previous related work, we consider heterogeneous agents with different rates of energy consumption (weights w_i). To solve the delivery problem, agents face three major challenges: Collaboration (how to work together on each message), Planning (which route to take) and Coordination (how to assign agents to messages). We first show that the delivery problem can be 2-approximated without collaborating and that this is best possible, i.e., we show that the benefit of collaboration is 2 in general. We also show that the benefit of collaboration for a single message is 1 / log 2 which is approximately 1.44. Planning turns out to be NP-hard to approximate even for a single agent, but can be 2-approximated in polynomial time if agents have unit capacities and do not collaborate. We further show that coordination is NP-hard even for agents with unit capacity, but can be efficiently solved exactly if they additionally have uniform weights. Finally, we give a polynomial-time c-approximation for message delivery with unit capacities.
Cite as

Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld, and Paolo Penna. Energy-Efficient Delivery by Heterogeneous Mobile Agents. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bartschi_et_al:LIPIcs.STACS.2017.10,
  author =	{B\"{a}rtschi, Andreas and Chalopin, J\'{e}r\'{e}mie and Das, Shantanu and Disser, Yann and Graf, Daniel and Hackfeld, Jan and Penna, Paolo},
  title =	{{Energy-Efficient Delivery by Heterogeneous Mobile Agents}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{10:1--10:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.10},
  URN =		{urn:nbn:de:0030-drops-70233},
  doi =		{10.4230/LIPIcs.STACS.2017.10},
  annote =	{Keywords: message delivery, mobile agents, energy optimization, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.153
Telling convex from reflex allows to map a polygon

Authors: Jeremie Chalopin, Shantanu Das, Yann Disser, Matus Mihalak, and Peter Widmayer

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We consider the exploration of a simple polygon P by a robot that moves from vertex to vertex along edges of the visibility graph of P. The visibility graph has a vertex for every vertex of P and an edge between two vertices if they see each other, i.e.~if the line segment connecting them lies inside $P$ entirely. While located at a vertex, the robot is capable of ordering the vertices it sees in counter-clockwise order as they appear on the boundary, and for every two such vertices, it can distinguish whether the angle between them is convex (<= pi) or reflex (> pi). Other than that, distant vertices are indistinguishable to the robot. We assume that an upper bound on the number of vertices is known and show that the robot is always capable of reconstructing the visibility graph of P. We also show that multiple identical, indistinguishable and deterministic such robots can always position themselves such that they mutually see each other, i.e. such that they form a clique in the visibility graph.
Cite as

Jeremie Chalopin, Shantanu Das, Yann Disser, Matus Mihalak, and Peter Widmayer. Telling convex from reflex allows to map a polygon. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 153-164, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.STACS.2011.153,
  author =	{Chalopin, Jeremie and Das, Shantanu and Disser, Yann and Mihalak, Matus and Widmayer, Peter},
  title =	{{Telling convex from reflex allows to map a polygon}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{153--164},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.153},
  URN =		{urn:nbn:de:0030-drops-30077},
  doi =		{10.4230/LIPIcs.STACS.2011.153},
  annote =	{Keywords: polygon mapping, map construction, autonomous agent, simple robot, visibility graph reconstruction}
}
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 Imprint Privacy Contact