13 Search Results for "Czyzowicz, Jurek"

Document
DOI: 10.4230/LIPIcs.STACS.2026.18
Optimal Deterministic Rendezvous in Labeled Lines

Authors: Yann Bourreau, Ananth Narayanan, and Alexandre Nolin

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In a rendezvous task, a set of mobile agents initially dispersed in a network have to gather at an arbitrary common site. We consider the rendezvous problem on the infinite labeled line, with 2 initially asleep agents, without communication, and a synchronous notion of time. Each node on the line is labeled with a unique positive integer. The initial distance between the two agents is denoted by D. Time is divided into rounds and measured from the moment an agent first wakes up. We denote by τ the delay between the two agents' wake up times. If awake in a given round T, an agent at a node v has three options: stay at the node v, take port 0, or take port 1. If it decides to stay, the agent will still be at node v in round T+1. Otherwise, it will be at one of the two neighbors of v on the infinite line, depending on the port it chose. The agents achieve rendezvous in T rounds if they are at the same node in round T. We aim for a deterministic algorithm for this problem. The problem was recently considered by Miller and Pelc [Distributed Computing, 2025]. With 𝓁_{max} the largest label of the two starting nodes, they showed that no algorithm can guarantee rendezvous in o(D log^* 𝓁_{max}) rounds. The lower bound follows from a connection with the LOCAL model of distributed computing, and holds even if the agents are guaranteed simultaneous wake-up (τ = 0) and are told their initial distance D. Miller and Pelc also gave an algorithm of optimal matching complexity O(D log^* 𝓁_{max}) when the agents know D, but only obtained the higher bound of O(D² (log^* 𝓁_{max})³) when D is unknown to the agents. In this paper, we improve this second complexity to a tight O(D log^* 𝓁_{max}), closing the gap between the best known lower and upper bounds. In fact, our algorithm achieves rendezvous in O(D log^* 𝓁_{min}) rounds, where 𝓁_{min} is the smallest label within distance O(D) of the two starting positions. We obtain this result by having the agents compute sparse subsets of the nodes to gather at (formally, ruling sets over the line), as well as some general observations about the setting of rendezvous on labeled graphs.
Cite as

Yann Bourreau, Ananth Narayanan, and Alexandre Nolin. Optimal Deterministic Rendezvous in Labeled Lines. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bourreau_et_al:LIPIcs.STACS.2026.18,
  author =	{Bourreau, Yann and Narayanan, Ananth and Nolin, Alexandre},
  title =	{{Optimal Deterministic Rendezvous in Labeled Lines}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.18},
  URN =		{urn:nbn:de:0030-drops-255071},
  doi =		{10.4230/LIPIcs.STACS.2026.18},
  annote =	{Keywords: mobile agents, rendezvous, ruling set, deterministic algorithms, labeled line}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.23
The Price of Connectivity Augmentation on Planar Graphs

Authors: Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Given two classes of graphs, 𝒢₁ ⊆ 𝒢₂, and a c-connected graph G ∈ 𝒢₁, we wish to augment G with a smallest cardinality set of new edges F to obtain a k-connected graph G' = (V,E∪ F) ∈ 𝒢₂. In general, this is the c → k connectivity augmentation problem. Previous research considered variants where 𝒢₁ = 𝒢₂ is the class of planar graphs, plane graphs, or planar straight-line graphs. In all three settings, we prove that the c → k augmentation problem is NP-complete when 2 ≤ c < k ≤ 5. However, the connectivity of the augmented graph G' is at most 5 if 𝒢₂ is limited to planar graphs. We initiate the study of the c → k connectivity augmentation problem for arbitrary k ∈ ℕ, where 𝒢₁ is the class of planar graphs, plane graphs, or planar straight-line graphs, and 𝒢₂ is a beyond-planar class of graphs: 𝓁-planar, 𝓁-plane topological, or 𝓁-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity k and the local crossing number 𝓁 of the augmented graph G'. We also show that our hardness results apply to this setting. The connectivity augmentation problem for triangulations is intimately related to edge flips; and the minimum augmentation problem to the flip distance between triangulations. We prove that it is NP-complete to find the minimum flip distance between a given triangulation and a 4-connected triangulation, settling an open problem posed in 2014, and present an EPTAS for this problem.
Cite as

Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt. The Price of Connectivity Augmentation on Planar Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.GD.2025.23,
  author =	{A. Akitaya, Hugo and Dallant, Justin and Demaine, Erik D. and Kaufmann, Michael and Kleist, Linda and Stock, Frederick and T\'{o}th, Csaba D. and Ueckerdt, Torsten},
  title =	{{The Price of Connectivity Augmentation on Planar Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{23:1--23:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.23},
  URN =		{urn:nbn:de:0030-drops-250095},
  doi =		{10.4230/LIPIcs.GD.2025.23},
  annote =	{Keywords: connectivity augmentation, local crossing number, flip distance}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.33
Approach of Agents with Restricted Fuel Tanks

Authors: Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak

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

Abstract
Two mobile agents, modelled as points in the plane moving at speed 1, have to get at a distance at most 1 from each other. This task is known as approach or rendezvous in the plane. An adversary initially places both agents at distinct points, called their bases, at distance at most D, and wakes them up at possibly different times. Each of the agents has a fuel tank that allows them to traverse a trajectory of length D, and can be replenished at the base of the agent. The algorithm of each agent consists of a series of actions which are either moves at a chosen distance in a chosen direction or staying idle for a chosen period of time. For a given instance of the approach task, the execution time of an approach algorithm is the length of the period between the start of the later agent and the moment of approach. Our goal is to design approach algorithms with optimal time complexity. We consider two independent coherence assumptions. One of them is time coherence, i.e., agents start simultaneously, and the other is orientation coherence: agents have compatible compasses, showing the same North direction. Our main result is establishing optimal time complexity of the approach problem with restricted fuel tanks. It turns out that this optimal complexity heavily depends on the above coherence assumptions. If both of them are satisfied then approach can be performed in time O(D²) and we show that this complexity is optimal. If any of the two coherence assumptions is missing then approach can be performed in time O(D²√D) and we prove that this order of magnitude cannot be improved. Our main technical contribution are lower bounds showing that, for each of the considered scenarios, our fairly natural approach algorithms are, in fact, optimal.
Cite as

Adam Ganczorz, Tomasz Jurdzinski, Andrzej Pelc, and Grzegorz Stachowiak. Approach of Agents with Restricted Fuel Tanks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 33:1-33:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2025.33,
  author =	{Ganczorz, Adam and Jurdzinski, Tomasz and Pelc, Andrzej and Stachowiak, Grzegorz},
  title =	{{Approach of Agents with Restricted Fuel Tanks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{33:1--33:22},
  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.33},
  URN =		{urn:nbn:de:0030-drops-248506},
  doi =		{10.4230/LIPIcs.DISC.2025.33},
  annote =	{Keywords: mobile agent, approach, rendezvous, plane, restricted energy}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.16
Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole

Authors: Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, and Partha Sarathi Mandal

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

Abstract
In this paper, we investigate the following question: "How can a group of initially co-located mobile agents perpetually explore an unknown graph, when one stationary node occasionally behaves maliciously, under the control of an adversary?" This malicious node is termed as "Byzantine black hole (BBH)" and at any given round it may choose to destroy all visiting agents, or none of them. While investigating this question, we found out that this subtle power turns out to drastically undermine even basic exploration strategies which have been proposed in the context of a classical, always active, black hole. We study this perpetual exploration problem in the presence of at most one BBH, without initial knowledge of the network size. Since the underlying graph may be 1-connected, perpetual exploration of the entire graph may be infeasible. Accordingly, we define two variants of the problem, termed as PerpExploration-BBH and PerpExploration-BBH-Home. In the former, the agents are tasked to perform perpetual exploration of at least one component, obtained after the exclusion of the BBH. In the latter, the agents are tasked to perform perpetual exploration of the component which contains the home node, where agents are initially co-located. Naturally, PerpExploration-BBH-Home is a special case of PerpExploration-BBH. The mobile agents are controlled by a synchronous scheduler, and they communicate via face-to-face model of communication. The main objective in this paper is to determine the minimum number of agents necessary and sufficient to solve these problems. We first consider the problems in acyclic networks, and we obtain optimal algorithms that solve PerpExploration-BBH with 4 agents, and PerpExploration-BBH-Home with 6 agents in trees. The lower bounds hold even in path graphs. In general graphs, we give a non-trivial lower bound of 2Δ-1 agents for PerpExploration-BBH, and an upper bound of 3Δ+3 agents for PerpExploration-BBH-Home. To the best of our knowledge, this is the first paper that studies a variant of a black hole in arbitrary networks, without initial topological knowledge about the network.
Cite as

Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, and Partha Sarathi Mandal. Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.DISC.2025.16,
  author =	{Bhattacharya, Adri and Goswami, Pritam and Bampas, Evangelos and Mandal, Partha Sarathi},
  title =	{{Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{16:1--16:17},
  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.16},
  URN =		{urn:nbn:de:0030-drops-248333},
  doi =		{10.4230/LIPIcs.DISC.2025.16},
  annote =	{Keywords: mobile agents, perpetual exploration, malicious host, Byzantine black hole}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.17
Perpetual Exploration of a Ring in Presence of Byzantine Black Hole

Authors: Pritam Goswami, Adri Bhattacharya, Raja Das, and Partha Sarathi Mandal

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Perpetual exploration stands as a fundamental problem in the domain of distributed mobile agent algorithms, where the objective is to ensure that each node within a graph is visited by at least one agent infinitely often. While this issue has received significant attention, particularly concerning ring topologies, the presence of malicious nodes, referred to as black holes, adds more complexity. A black hole can destroy any incoming agent without leaving any trace of its existence. In [Bampas et al., 2015; Královič and Miklík, 2010], the authors have considered this problem in the context of periodic data retrieval. They introduced a variant of a black hole called gray hole (where the adversary chooses whether to destroy an agent or let it pass) among other variants, and showed that 4 asynchronous and co-located agents are necessary and sufficient to solve the periodic data retrieval problem (hence perpetual exploration) in the presence of such a gray hole if each of the nodes of the ring has a whiteboard. This paper investigates the exploration of a ring by introducing a realistic variant of a gray hole, called a "Byzantine black hole". In addition to the usual capabilities of a gray hole, the adversary can also choose whether to erase any previously stored information on that node. Note that in [Bampas et al., 2015; Královič and Miklík, 2010], this problem was considered with only one particular initial scenario (i.e., agents are initially co-located) and one specific communication model (i.e., whiteboard). Now, there can be many other initial scenarios where all agents might not be co-located (i.e., they may be scattered). Also, there are many weaker communications models such as Face-to-Face and Pebble, where this perpetual exploration problem is yet to be investigated in the presence of a Byzantine black hole. The main results of our paper focus on minimizing the number of agents while guaranteeing that they perform the perpetual exploration on a ring even in the presence of a Byzantine black hole under different communication models and for different starting scenarios. On the positive side, as a byproduct of our work, we achieved a better upper and lower bound result (i.e., 3 agents) for perpetual exploration in the presence of a Byzantine black hole (which is a more generalized version of a gray hole), by trading-off the scheduler capability, when the agents are initially co-located, and each node contains a whiteboard.
Cite as

Pritam Goswami, Adri Bhattacharya, Raja Das, and Partha Sarathi Mandal. Perpetual Exploration of a Ring in Presence of Byzantine Black Hole. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{goswami_et_al:LIPIcs.OPODIS.2024.17,
  author =	{Goswami, Pritam and Bhattacharya, Adri and Das, Raja and Mandal, Partha Sarathi},
  title =	{{Perpetual Exploration of a Ring in Presence of Byzantine Black Hole}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.17},
  URN =		{urn:nbn:de:0030-drops-225532},
  doi =		{10.4230/LIPIcs.OPODIS.2024.17},
  annote =	{Keywords: Mobile Agents, Exploration, Ring, Black Hole, Malicious host, Byzantine Fault}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.11
Gathering Teams of Deterministic Finite Automata on a Line

Authors: Younan Gao and Andrzej Pelc

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
Several mobile agents, modelled as deterministic finite automata, navigate in an infinite line in synchronous rounds. All agents start in the same round. In each round, an agent can move to one of the two neighboring nodes, or stay idle. Agents have distinct labels which are integers from the set {1,…,L}. They start in teams, each of which consists of x agents, for some fixed integer x. Agents in a team have the same starting node. The adversary decides the compositions of teams, and their starting nodes. Whenever an agent enters a node, it sees the entry port number and the states of all collocated agents; this information forms the input of the agent on the basis of which it transits to the next state and decides the current action. The aim is for all agents to gather at the same node and stop. Gathering is feasible, if this task can be accomplished for any decisions of the adversary, and its time is the worst-case number of rounds from the start till gathering. We consider the feasibility and time complexity of gathering teams of agents, and give a complete solution of this problem. It turns out that both feasibility and complexity of gathering depend on the crucial parameter x which is the size of teams. For the oriented line, gathering is impossible if x = 1, and it can be accomplished in time O(D), for x > 1, where D is the distance between the starting nodes of the most distant teams. This complexity is of course optimal. For the unoriented line, the situation is different. For x = 1, gathering is also impossible, but for x = 2, the optimal time of gathering is Θ(Dlog L), and for x ≥ 3 the optimal time of gathering is Θ(D). Solving the gathering problem for agents that are finite automata navigating in an infinite environment requires new methodological tools. Traditional gathering techniques in graphs are count driven: agents make decisions based on counting steps. Since distances between agents may be unbounded, agents have to count unbounded numbers of steps. When agents are finite automata, counting unbounded numbers of steps is impossible, hence we must use different methods. In all our gathering algorithms, changes of the agents' behavior are triggered not by counting steps but by events which are meetings between agents during which they interact. Hence our new technique is event driven. Designing the behavior of the agents based on meeting events, so as to guarantee gathering regardless of the adversary’s decisions is our main methodological contribution.
Cite as

Younan Gao and Andrzej Pelc. Gathering Teams of Deterministic Finite Automata on a Line. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.OPODIS.2024.11,
  author =	{Gao, Younan and Pelc, Andrzej},
  title =	{{Gathering Teams of Deterministic Finite Automata on a Line}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.11},
  URN =		{urn:nbn:de:0030-drops-225478},
  doi =		{10.4230/LIPIcs.OPODIS.2024.11},
  annote =	{Keywords: Gathering, deterministic finite automaton, mobile agent, team of agents, line, time}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.9
Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents

Authors: Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
We consider the problem of graph exploration by energy sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and the considered topology is that of connected acyclic graphs (i.e. trees). We consider both the asynchronous and the synchronous settings, and we provide necessary and sufficient conditions about the energy.
Cite as

Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil. Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.OPODIS.2024.9,
  author =	{Bramas, Quentin and Masuzawa, Toshimitsu and Tixeuil, S\'{e}bastien},
  title =	{{Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.9},
  URN =		{urn:nbn:de:0030-drops-225452},
  doi =		{10.4230/LIPIcs.OPODIS.2024.9},
  annote =	{Keywords: Mobile Agents, Distributed Algorithms, Energy sharing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.57
Group Evacuation on a Line by Agents with Different Communication Abilities

Authors: Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, and Sunil Shende

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We consider evacuation of a group of n ≥ 2 autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed 1 in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitive ratio (CR) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio CR = 3+2√2. If there is a single sender or fully wireless agent, and multiple receivers we prove that CR ∈ [2+√5,5], and if there are multiple senders and a single receiver or fully wireless agent, we show that CR ∈ [3,5.681319]. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3.
Cite as

Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, and Sunil Shende. Group Evacuation on a Line by Agents with Different Communication Abilities. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 57:1-57:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{czyzowicz_et_al:LIPIcs.ISAAC.2021.57,
  author =	{Czyzowicz, Jurek and Killick, Ryan and Kranakis, Evangelos and Krizanc, Danny and Narayanan, Lata and Opatrny, Jaroslav and Pankratov, Denis and Shende, Sunil},
  title =	{{Group Evacuation on a Line by Agents with Different Communication Abilities}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{57:1--57:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.57},
  URN =		{urn:nbn:de:0030-drops-154903},
  doi =		{10.4230/LIPIcs.ISAAC.2021.57},
  annote =	{Keywords: Agent, Communication, Evacuation, Mobile, Receiver, Search, Sender}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.35
Building a Nest by an Automaton

Authors: Jurek Czyzowicz, Dariusz Dereniowski, and Andrzej Pelc

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
A robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid Z x Z. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the field, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its span. The robot starts at a full cell. It can carry at most one brick at a time. At each step it can pick a brick from a full cell, move to an adjacent cell and drop a brick at an empty cell. The aim of the robot is to construct the most compact possible structure composed of all bricks, i.e., a nest. That is, the robot has to move all bricks in such a way that the span of the resulting field be the smallest. Our main result is the design of a deterministic finite automaton that accomplishes this task and subsequently stops, for every initially connected field, in time O(sz), where s is the span of the initial field and z is the number of bricks. We show that this complexity is optimal.
Cite as

Jurek Czyzowicz, Dariusz Dereniowski, and Andrzej Pelc. Building a Nest by an Automaton. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{czyzowicz_et_al:LIPIcs.ESA.2019.35,
  author =	{Czyzowicz, Jurek and Dereniowski, Dariusz and Pelc, Andrzej},
  title =	{{Building a Nest by an Automaton}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{35:1--35:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.35},
  URN =		{urn:nbn:de:0030-drops-111564},
  doi =		{10.4230/LIPIcs.ESA.2019.35},
  annote =	{Keywords: finite automaton, plane, grid, construction task, brick, mobile agent, robot}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.137
Energy Consumption of Group Search on a Line

Authors: Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can collaborate in the search, but can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of d, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least 9d - o(d); a simple doubling strategy achieves this time bound. It was shown recently in [Chrobak et al., 2015] that k >= 2 robots traveling at unit speed also require at least 9d group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance x at constant speed s is given by s^2 x, as motivated by energy consumption models in physics and engineering. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple c of the distance d and the speed of the robots is bounded by b. Motivation for this study is that for the case when robots must complete the search in 9d time with maximum speed one (b=1; c=9), a single robot requires at least 9d energy, while for two robots, all previously proposed algorithms consume at least 28d/3 energy. When the robots have bounded memory and can use only a constant number of fixed speeds, we generalize an algorithm described in [Baeza-Yates and Schott, 1995; Chrobak et al., 2015] to obtain a family of algorithms parametrized by pairs of b,c values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. In particular, for each such pair, we determine optimal (and in some cases nearly optimal) algorithms inducing the lowest possible energy consumption. We also propose a novel search algorithm that simultaneously achieves search time 9d and consumes energy 8.42588d. Our result shows that two robots can search on the line in optimal time 9d while consuming less total energy than a single robot within the same search time. Our algorithm uses robots that have unbounded memory, and a finite number of dynamically computed speeds. It can be generalized for any c, b with cb=9, and consumes energy 8.42588b^2d.
Cite as

Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende. Energy Consumption of Group Search on a Line. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 137:1-137:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{czyzowicz_et_al:LIPIcs.ICALP.2019.137,
  author =	{Czyzowicz, Jurek and Georgiou, Konstantinos and Killick, Ryan and Kranakis, Evangelos and Krizanc, Danny and Lafond, Manuel and Narayanan, Lata and Opatrny, Jaroslav and Shende, Sunil},
  title =	{{Energy Consumption of Group Search on a Line}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{137:1--137:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.137},
  URN =		{urn:nbn:de:0030-drops-107138},
  doi =		{10.4230/LIPIcs.ICALP.2019.137},
  annote =	{Keywords: Evacuation, Exit, Line, Face-to-face Communication, Robots, Search}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.25
Linear Rendezvous with Asymmetric Clocks

Authors: Jurek Czyzowicz, Ryan Killick, and Evangelos Kranakis

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
Two anonymous robots placed at different positions on an infinite line need to rendezvous. Each robot possesses a clock which it uses to time its movement. However, the robot's individual parameters in the form of their walking speed and time unit may or may not be the same for both robots. We study the feasibility of rendezvous in different scenarios, in which some subsets of these parameters are not the same. As the robots are anonymous, they execute the same algorithm and when both parameters are identical the rendezvous is infeasible. We propose a universal algorithm, such that the robots are assured of meeting in finite time, in any case when at least one of the parameters is not equal for both robots.
Cite as

Jurek Czyzowicz, Ryan Killick, and Evangelos Kranakis. Linear Rendezvous with Asymmetric Clocks. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{czyzowicz_et_al:LIPIcs.OPODIS.2018.25,
  author =	{Czyzowicz, Jurek and Killick, Ryan and Kranakis, Evangelos},
  title =	{{Linear Rendezvous with Asymmetric Clocks}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.25},
  URN =		{urn:nbn:de:0030-drops-100855},
  doi =		{10.4230/LIPIcs.OPODIS.2018.25},
  annote =	{Keywords: anonymous, asymmetric clock, infinite line, rendezvous, mobile robot, speed, competitive ratio}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.16
God Save the Queen

Authors: Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Queen Daniela of Sardinia is asleep at the center of a round room at the top of the tower in her castle. She is accompanied by her faithful servant, Eva. Suddenly, they are awakened by cries of "Fire". The room is pitch black and they are disoriented. There is exactly one exit from the room somewhere along its boundary. They must find it as quickly as possible in order to save the life of the queen. It is known that with two people searching while moving at maximum speed 1 anywhere in the room, the room can be evacuated (i.e., with both people exiting) in 1 + (2 pi)/3 + sqrt{3} ~~ 4.8264 time units and this is optimal [Czyzowicz et al., DISC'14], assuming that the first person to find the exit can directly guide the other person to the exit using her voice. Somewhat surprisingly, in this paper we show that if the goal is to save the queen (possibly leaving Eva behind to die in the fire) there is a slightly better strategy. We prove that this "priority" version of evacuation can be solved in time at most 4.81854. Furthermore, we show that any strategy for saving the queen requires time at least 3 + pi/6 + sqrt{3}/2 ~~ 4.3896 in the worst case. If one or both of the queen's other servants (Biddy and/or Lili) are with her, we show that the time bounds can be improved to 3.8327 for two servants, and 3.3738 for three servants. Finally we show lower bounds for these cases of 3.6307 (two servants) and 3.2017 (three servants). The case of n >= 4 is the subject of an independent study by Queen Daniela's Royal Scientific Team.
Cite as

Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende. God Save the Queen. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{czyzowicz_et_al:LIPIcs.FUN.2018.16,
  author =	{Czyzowicz, Jurek and Georgiou, Konstantinos and Killick, Ryan and Kranakis, Evangelos and Krizanc, Danny and Narayanan, Lata and Opatrny, Jaroslav and Shende, Sunil},
  title =	{{God Save the Queen}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.16},
  URN =		{urn:nbn:de:0030-drops-88074},
  doi =		{10.4230/LIPIcs.FUN.2018.16},
  annote =	{Keywords: Algorithm, Evacuation, Exit, Disk, Wireless Communication, Queen, Priority, Robots, Search, Servants, Trajectory}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.27
Search on a Line by Byzantine Robots

Authors: Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We consider the problem of fault-tolerant parallel search on an infinite line by n robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed 1 and can communicate in wireless mode among themselves. However, among the n robots, there are f robots that exhibit byzantine faults. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient verification that the target has been found. We aim to design algorithms that minimize the value of S_d (n, f), the time to find a target at a distance d from the origin by n robots among which f are faulty. We give several different algorithms whose running time depends on the ratio f/n, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.
Cite as

Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende. Search on a Line by Byzantine Robots. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 27:1-27:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{czyzowicz_et_al:LIPIcs.ISAAC.2016.27,
  author =	{Czyzowicz, Jurek and Georgiou, Konstantinos and Kranakis, Evangelos and Krizanc, Danny and Narayanan, Lata and Opatrny, Jaroslav and Shende, Sunil},
  title =	{{Search on a Line by Byzantine Robots}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{27:1--27:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.27},
  URN =		{urn:nbn:de:0030-drops-67972},
  doi =		{10.4230/LIPIcs.ISAAC.2016.27},
  annote =	{Keywords: Cow path problem, Parallel search, Mobile robots, Wireless communication, Byzantine faults}
}
  • Refine by Type
  • 13 Document/PDF
  • 7 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 6 2025
  • 1 2021
  • 3 2019
  • 1 2018
  • Show More...

  • Refine by Author
  • 6 Czyzowicz, Jurek
  • 5 Kranakis, Evangelos
  • 4 Killick, Ryan
  • 4 Krizanc, Danny
  • 4 Narayanan, Lata
  • Show More...

  • Refine by Series/Journal
  • 13 LIPIcs

  • Refine by Classification
  • 7 Theory of computation → Distributed algorithms
  • 3 Computing methodologies → Mobile agents
  • 3 Theory of computation → Design and analysis of algorithms
  • 1 Computing methodologies → Distributed artificial intelligence
  • 1 Mathematics of computing → Graph algorithms
  • Show More...

  • Refine by Keyword
  • 3 Evacuation
  • 3 Search
  • 3 mobile agent
  • 3 rendezvous
  • 2 Exit
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact