2 Search Results for "Giachoudis, Nikos"

Document
DOI: 10.4230/LIPIcs.ISAAC.2022.19
Evacuation from a Disk for Robots with Asymmetric Communication

Authors: Konstantinos Georgiou, Nikos Giachoudis, and Evangelos Kranakis

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We consider evacuation of two robots from an Exit placed at an unknown location on the perimeter of a unit (radius) disk. The robots can move with max speed 1 and start at the center of the disk at the same time. We consider a new communication model, known as the SR model, in which the robots have communication faults as follows: one of the robots is a Sender and can only send wirelessly at any distance, while the other is a Receiver in that it can only receive wirelessly from any distance. The communication status of each robot is known to the other robot. In addition, both robots can exchange messages when they are co-located, which is known as Face-to-Face (F2F) model. There have been several studies in the literature concerning the evacuation time when both robots may employ either F2F or Wireless (WiFi) communication. The SR communication model diverges from these two in that the two robots themselves have differing communication capabilities. We study the evacuation time, namely the time it takes until the last robot reaches the Exit, and show that the evacuation time in the SR model is strictly between the F2F and the WiFi models. The main part of our technical contribution is also an evacuation algorithm in which two cooperating robots accomplish the task in worst-case time at most π+2. Interesting features of the proposed algorithm are the asymmetry inherent in the resulting trajectories, as well as that the robots do not move at full speed for the entire duration of their trajectories.
Cite as

Konstantinos Georgiou, Nikos Giachoudis, and Evangelos Kranakis. Evacuation from a Disk for Robots with Asymmetric Communication. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{georgiou_et_al:LIPIcs.ISAAC.2022.19,
  author =	{Georgiou, Konstantinos and Giachoudis, Nikos and Kranakis, Evangelos},
  title =	{{Evacuation from a Disk for Robots with Asymmetric Communication}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{19:1--19:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.19},
  URN =		{urn:nbn:de:0030-drops-173047},
  doi =		{10.4230/LIPIcs.ISAAC.2022.19},
  annote =	{Keywords: Communication, Cycle, Evacuation, Receiver, Sender, Mobile Agents}
}
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-dev.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}
}
  • Refine by Author
  • 2 Giachoudis, Nikos
  • 1 Das, Shantanu
  • 1 Georgiou, Konstantinos
  • 1 Kranakis, Evangelos
  • 1 Luccio, Flaminia L.
  • Show More...

  • Refine by Classification
  • 1 Networks → Network algorithms
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Distributed algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 2 Mobile Agents
  • 1 Broadcast
  • 1 Communication
  • 1 Constantly Connected
  • 1 Cycle
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2021
  • 1 2022

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