DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2023.29

Fast Deterministic Rendezvous in Labeled Lines

Authors: Avery Miller and Andrzej Pelc

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract

Two mobile agents, starting from different nodes of a network modeled as a graph, and woken up at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds. In each round, an agent can either stay idle or move to an adjacent node. We consider deterministic rendezvous in the infinite line, i.e., the infinite graph with all nodes of degree 2. Each node has a distinct label which is a positive integer. An agent currently located at a node can see its label and both ports 0 and 1 at the node. The time of rendezvous is the number of rounds until meeting, counted from the starting round of the earlier agent. We consider three scenarios. In the first scenario, each agent knows its position in the line, i.e., each of them knows its initial distance from the smallest-labeled node, on which side of this node it is located, and the direction towards it. For this scenario, we design a rendezvous algorithm working in time O(D), where D is the initial distance between the agents. This complexity is clearly optimal. In the second scenario, each agent knows a priori only the label of its starting node and the initial distance D between them. In this scenario, we design a rendezvous algorithm working in time O(Dlog^*𝓁), where 𝓁 is the larger label of the starting nodes. We also prove a matching lower bound Ω(Dlog^*𝓁). Finally, in the most general scenario, where each agent knows a priori only the label of its starting node, we design a rendezvous algorithm working in time O(D²(log^*𝓁)³), which is thus at most cubic in the lower bound. All our results remain valid (with small changes) for arbitrary finite lines and for cycles. Our algorithms are drastically better than approaches that use graph exploration, which have running times that depend on the size or diameter of the graph. Our main methodological tool, and the main novelty of the paper, is a two way reduction: from fast colouring of the infinite labeled line using a constant number of colours in the LOCAL model to fast rendezvous in this line, and vice-versa. In one direction we use fast node colouring to quickly break symmetry between the identical agents. In the other direction, a lower bound on colouring time implies a lower bound on the time of breaking symmetry between the agents, and hence a lower bound on their meeting time.

Cite as

Avery Miller and Andrzej Pelc. Fast Deterministic Rendezvous in Labeled Lines. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{miller_et_al:LIPIcs.DISC.2023.29,
  author =	{Miller, Avery and Pelc, Andrzej},
  title =	{{Fast Deterministic Rendezvous in Labeled Lines}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{29:1--29:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.29},
  URN =		{urn:nbn:de:0030-drops-191550},
  doi =		{10.4230/LIPIcs.DISC.2023.29},
  annote =	{Keywords: rendezvous, deterministic algorithm, mobile agent, labeled line, graph colouring}
}

Document

DOI: 10.4230/LIPIcs.DISC.2022.11

How to Meet at a Node of Any Connected Graph

Authors: Subhash Bhagat and Andrzej Pelc

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

Two mobile agents have to meet at the same node of a connected graph with unlabeled nodes. This intensely researched task is known as rendezvous. The adversary assigns the agents different starting nodes in the graph and different integer labels from a set {1,… ,L}. Time is slotted in synchronous rounds. The adversary wakes up the agents in possibly different rounds. After wakeup, the agents move as follows. In each round, an agent can either stay idle or move to an adjacent node. Each agent knows its label but not the label of the other agent, and agents have no a priori information about the graph. They do not know L. They execute the same deterministic algorithm whose parameter is the agent’s label. The time of a rendezvous algorithm is the worst-case number of rounds since the wakeup of the earlier agent till the meeting. In most of the results concerning rendezvous in graphs, the graph is finite and rendezvous relies on the exploration of the entire graph. Thus the time of rendezvous depends on the size of the graph. This approach is inefficient for very large graphs, and cannot be used for infinite graphs. For such graphs it is natural to seek rendezvous algorithms whose time depends on the initial distance D between the agents. In this paper we adopt this approach and consider rendezvous in arbitrary connected graphs with nodes of finite degrees, and whose set of nodes is finite or countably infinite. Our main result is the first deterministic rendezvous algorithm working under this general scenario. For any node v and any positive integer r, let P(v,r) be the number of paths of length r in the graph, starting at node v. For any instance of the rendezvous problem where agents start at nodes v₁ and v₂ at distance D, let P(v₁,v₂,D) = max(P(v₁,D),P(v₂,D)). It is well known that, for example in trees, Ω(D+P(v₁,v₂,D) +log L) is a lower bound on rendezvous time for such an instance. The time of our algorithm, working for arbitrary connected graphs of finite degrees, is polynomial in this lower bound. As an application we solve the problem of approach for synchronous agents in terrains in the plane, in time polynomial in log L and in the initial distance between the agents in the terrain.

Cite as

Subhash Bhagat and Andrzej Pelc. How to Meet at a Node of Any Connected Graph. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhagat_et_al:LIPIcs.DISC.2022.11,
  author =	{Bhagat, Subhash and Pelc, Andrzej},
  title =	{{How to Meet at a Node of Any Connected Graph}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.11},
  URN =		{urn:nbn:de:0030-drops-172024},
  doi =		{10.4230/LIPIcs.DISC.2022.11},
  annote =	{Keywords: Algorithm, graph, rendezvous, mobile agent, terrain}
}

Document

DOI: 10.4230/LIPIcs.DISC.2021.22

Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels

Authors: Adam Gańczorz, Tomasz Jurdziński, Mateusz Lewko, and Andrzej Pelc

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract

We consider the fundamental problems of size discovery and topology recognition in radio networks modeled by simple undirected connected graphs. Size discovery calls for all nodes to output the number of nodes in the graph, called its size, and in the task of topology recognition each node has to learn the topology of the graph and its position in it. We do not assume collision detection: in case of a collision, node v does not hear anything (except the background noise that it also hears when no neighbor transmits). The time of a deterministic algorithm for each of the above problems is the worst-case number of rounds it takes to solve it. Nodes have labels which are (not necessarily different) binary strings. Each node knows its own label and can use it when executing the algorithm. The length of a labeling scheme is the largest length of a label. For size discovery, we construct a labeling scheme of length O(log logΔ) (which is known to be optimal, even if collision detection is available) and we design an algorithm for this problem using this scheme and working in time O(log² n), where n is the size of the graph. We also show that time complexity O(log² n) is optimal for the problem of size discovery, whenever the labeling scheme is of optimal length O(log logΔ). For topology recognition, we construct a labeling scheme of length O(logΔ), and we design an algorithm for this problem using this scheme and working in time O (DΔ+min(Δ²,n)), where D is the diameter of the graph. We also show that the length of our labeling scheme is asymptotically optimal.

Cite as

Adam Gańczorz, Tomasz Jurdziński, Mateusz Lewko, and Andrzej Pelc. Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganczorz_et_al:LIPIcs.DISC.2021.22,
  author =	{Ga\'{n}czorz, Adam and Jurdzi\'{n}ski, Tomasz and Lewko, Mateusz and Pelc, Andrzej},
  title =	{{Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.22},
  URN =		{urn:nbn:de:0030-drops-148242},
  doi =		{10.4230/LIPIcs.DISC.2021.22},
  annote =	{Keywords: size discovery, topology recognition, radio network, labeling scheme}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2021.36

Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs

Authors: Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, and Andrzej Pelc

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract

A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [Baruch Awerbuch et al., 1999] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s. The size of the tank is B = 2(1+α)r, for some positive real constant α, where r, called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most {⌊ B⌋} edge traversals between two consecutive visits at node s. Let e(d) be the number of edges whose at least one extremity is at distance less than d from s. Awerbuch, Betke, Rivest and Singh [Baruch Awerbuch et al., 1999] conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e(d). We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost 𝒪(e(d) log d), and then show how to modify this algorithm to work in the model from [Baruch Awerbuch et al., 1999] with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost Θ(e(d)) for all graphs and thus our algorithms are also almost optimal.

Cite as

Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, and Andrzej Pelc. Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bouchard_et_al:LIPIcs.ICALP.2021.36,
  author =	{Bouchard, S\'{e}bastien and Dieudonn\'{e}, Yoann and Labourel, Arnaud and Pelc, Andrzej},
  title =	{{Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.36},
  URN =		{urn:nbn:de:0030-drops-141051},
  doi =		{10.4230/LIPIcs.ICALP.2021.36},
  annote =	{Keywords: treasure hunt, graph, mobile agent}
}

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-dev.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

DOI: 10.4230/LIPIcs.ISAAC.2018.48

Deterministic Treasure Hunt in the Plane with Angular Hints

Authors: Sébastien Bouchard, Yoann Dieudonné, Andrzej Pelc, and Franck Petit

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract

A mobile agent equipped with a compass and a measure of length has to find an inert treasure in the Euclidean plane. Both the agent and the treasure are modeled as points. In the beginning, the agent is at a distance at most D>0 from the treasure, but knows neither the distance nor any bound on it. Finding the treasure means getting at distance at most 1 from it. The agent makes a series of moves. Each of them consists in moving straight in a chosen direction at a chosen distance. In the beginning and after each move the agent gets a hint consisting of a positive angle smaller than 2 pi whose vertex is at the current position of the agent and within which the treasure is contained. We investigate the problem of how these hints permit the agent to lower the cost of finding the treasure, using a deterministic algorithm, where the cost is the worst-case total length of the agent's trajectory. It is well known that without any hint the optimal (worst case) cost is Theta(D^2). We show that if all angles given as hints are at most pi, then the cost can be lowered to O(D), which is optimal. If all angles are at most beta, where beta<2 pi is a constant unknown to the agent, then the cost is at most O(D^{2-epsilon}), for some epsilon>0. For both these positive results we present deterministic algorithms achieving the above costs. Finally, if angles given as hints can be arbitrary, smaller than 2 pi, then we show that cost Theta(D^2) cannot be beaten.

Cite as

Sébastien Bouchard, Yoann Dieudonné, Andrzej Pelc, and Franck Petit. Deterministic Treasure Hunt in the Plane with Angular Hints. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bouchard_et_al:LIPIcs.ISAAC.2018.48,
  author =	{Bouchard, S\'{e}bastien and Dieudonn\'{e}, Yoann and Pelc, Andrzej and Petit, Franck},
  title =	{{Deterministic Treasure Hunt in the Plane with Angular Hints}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{48:1--48:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.48},
  URN =		{urn:nbn:de:0030-drops-99964},
  doi =		{10.4230/LIPIcs.ISAAC.2018.48},
  annote =	{Keywords: treasure hunt, deterministic algorithm, mobile agent, hint, plane}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2017.132

Deterministic Graph Exploration with Advice

Authors: Barun Gorain and Andrzej Pelc

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract

We consider the task of graph exploration. An n-node graph has unlabeled nodes, and all ports at any node of degree d are arbitrarily numbered 0,..., d-1. A mobile agent has to visit all nodes and stop. The exploration time is the number of edge traversals. We consider the problem of how much knowledge the agent has to have a priori, in order to explore the graph in a given time, using a deterministic algorithm. This a priori information (advice) is provided to the agent by an oracle, in the form of a binary string, whose length is called the size of advice. We consider two types of oracles. The instance oracle knows the entire instance of the exploration problem, i.e., the port-numbered map of the graph and the starting node of the agent in this map. The map oracle knows the port-numbered map of the graph but does not know the starting node of the agent. What is the minimum size of advice that must be given to the agent by each of these oracles, so that the agent explores the graph in a given time? We first consider exploration in polynomial time, and determine the exact minimum size of advice to achieve it. This size is log(log(log(n))) - Theta(1), for both types of oracles. When advice is large, there are two natural time thresholds: Theta(n^2) for a map oracle, and Theta(n) for an instance oracle, that can be achieved with sufficiently large advice. We show that, with a map oracle, time Theta(n^2) cannot be improved in general, regardless of the size of advice. We also show that the smallest size of advice to achieve this time is larger than n^delta, for any delta <1/3. For an instance oracle, advice of size O(n*log(n)) is enough to achieve time O(n). We show that, with any advice of size o(n*log(n)), the time of exploration must be at least n^epsilon, for any epsilon <2, and with any advice of size O(n), the time must be Omega(n^2). We also investigate minimum advice sufficient for fast exploration of Hamiltonian graphs.

Cite as

Barun Gorain and Andrzej Pelc. Deterministic Graph Exploration with Advice. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 132:1-132:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gorain_et_al:LIPIcs.ICALP.2017.132,
  author =	{Gorain, Barun and Pelc, Andrzej},
  title =	{{Deterministic Graph Exploration with Advice}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{132:1--132:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.132},
  URN =		{urn:nbn:de:0030-drops-73701},
  doi =		{10.4230/LIPIcs.ICALP.2017.132},
  annote =	{Keywords: algorithm, graph, exploration, mobile agent, advice}
}

7 Search Results for "Pelc, Andrzej"

Fast Deterministic Rendezvous in Labeled Lines

Abstract

Cite as

How to Meet at a Node of Any Connected Graph

Abstract

Cite as

Deterministic Size Discovery and Topology Recognition in Radio Networks with Short Labels

Abstract

Cite as

Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs

Abstract

Cite as

Building a Nest by an Automaton

Abstract

Cite as

Deterministic Treasure Hunt in the Plane with Angular Hints

Abstract

Cite as

Deterministic Graph Exploration with Advice

Abstract

Cite as

Thanks for your feedback!

Could not send message