Deterministic rendezvous in infinite trees

DOI10.1016/J.TCS.2023.114313MaRDI QIDQ6140349zbMATH OpenFDO

Authors Subhash Bhagat, Andrzej Pelc

Publication date 2 January 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.05160

zbMATH Keywords

algorithmmobile agentrendezvoustree

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: The rendezvous task calls for two mobile agents, starting from different nodes of a network modeled as a graph to meet at the same node. Agents have different labels which are integers from a set $1,dots,L$. They wake up at possibly different times and move in synchronous rounds. In each round, an agent can either stay idle or move to an adjacent node. We consider deterministic rendezvous algorithms. The time of such an algorithm is the number of rounds since the wakeup of the earlier agent till the meeting. In this paper we consider rendezvous in infinite trees. Our main goal is to study the impact of orientation of a tree on the time of rendezvous. We first design a rendezvous algorithm working for unoriented regular trees, whose time is in $O(z(D)logL)$, where $z(D)$ is the size of the ball of radius $D$, i.e, the number of nodes at distance at most $D$ from a given node. The algorithm works for arbitrary delay between waking times of agents and does not require any initial information about parameters $L$ or $D$. Its disadvantage is its complexity: $z(D)$ is exponential in $D$ for any degree $d>2$ of the tree. We prove that this high complexity is inevitable: $Omega(z(D))$ turns out to be a lower bound on rendezvous time in unoriented regular trees, even for simultaneous start and even when agents know $L$ and $D$. Then we turn attention to oriented trees. While for arbitrary delay between waking times of agents the lower bound $Omega(z(D))$ still holds, for simultaneous start the time of rendezvous can be dramatically shortened. We show that if agents know either a polynomial upper bound on $L$ or a linear upper bound on $D$, then rendezvous can be accomplished in oriented trees in time $O(DlogL)$, which is optimal. When no such extra knowledge is available, we design an algorithm working in time $O(D^2+lo{g}^{2}L)$.

Cites work

• Almost optimal asynchronous rendezvous in infinite multidimensional grids
• Anonymous meeting in networks
• Asynchronous approach in the plane: a deterministic polynomial algorithm
• Asynchronous deterministic rendezvous in graphs
• Delays induce an exponential memory gap for rendezvous in trees
• Deterministic rendezvous in graphs
• Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences
• Distributed computing by mobile robots: gathering
• Gathering of asynchronous robots with limited visibility
• How to meet in anonymous network
• How to meet when you forget: log-space rendezvous in arbitrary graphs
• LATIN 2004: Theoretical Informatics
• Minimax Rendezvous on the Line
• Operations research/management science at work.
• Randomized Rendez-Vous with Limited Memory
• Rendezvous on the Line when the Players' Initial Distance is Given by an Unknown Probability Distribution
• Rendezvous search when marks are left at the starting points
• Symmetry Breaking in the Plane
• Synchronous rendezvous for location-aware agents
• The Rendezvous Search Problem
• Two Dimensional Rendezvous Search

Cited in

(1)

• Sniffing helps to meet: deterministic rendezvous of anonymous agents in the grid

This page was built for publication: Deterministic rendezvous in infinite trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6140349)