Fast rendezvous with advice

DOI10.1016/J.TCS.2015.09.025zbMATH Open1333.68068OpenAlexW2163134916MaRDI QIDQ896137FDOQ896137

Authors Avery Miller, Andrzej Pelc

Publication date 11 December 2015

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

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

zbMATH Keywords

timeadvicemobile agentrendezvousdeterministic distributed algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Agent technology and artificial intelligence (68T42) Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: Two mobile agents, starting from different nodes of an $n$-node network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds using a deterministic algorithm. In each round, an agent decides to either remain idle or to move to one of the adjacent nodes. Each agent has a distinct integer label from the set $1,\mathrm{...},L$, which it can use in the execution of the algorithm, but it does not know the label of the other agent. If $D$ is the distance between the initial positions of the agents, then $Omega(D)$ is an obvious lower bound on the time of rendezvous. However, if each agent has no initial knowledge other than its label, time $O(D)$ is usually impossible to achieve. We study the minimum amount of information that has to be available a priori to the agents to achieve rendezvous in optimal time $Theta(D)$. This information is provided to the agents at the start by an oracle knowing the entire instance of the problem, i.e., the network, the starting positions of the agents, their wake-up rounds, and both of their labels. The oracle helps the agents by providing them with the same binary string called advice, which can be used by the agents during their navigation. The length of this string is called the size of advice. Our goal is to find the smallest size of advice which enables the agents to meet in time $Theta(D)$. We show that this optimal size of advice is $Theta(Dlog(n/D)+loglogL)$. The upper bound is proved by constructing an advice string of this size, and providing a natural rendezvous algorithm using this advice that works in time $Theta(D)$ for all networks. The matching lower bound, which is the main contribution of this paper, is proved by exhibiting classes of networks for which it is impossible to achieve rendezvous in time $Theta(D)$ with smaller advice.

Recommendations

• Time versus cost tradeoffs for deterministic rendezvous in networks
• Deterministic rendezvous in graphs
• Time versus space trade-offs for rendezvous in trees
• Time versus cost tradeoffs for deterministic rendezvous in networks
• Rendezvous of distance-aware mobile agents in unknown graphs

Cites work

• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• Almost optimal asynchronous rendezvous in infinite multidimensional grids
• Approximate distance oracles
• Asynchronous deterministic rendezvous in graphs
• Communication algorithms with advice
• Compact labeling schemes for ancestor queries. (Extended abstract)
• Delays induce an exponential memory gap for rendezvous in trees
• Deterministic rendezvous in graphs
• Deterministic rendezvous, treasure hunts and strongly universal exploration sequences
• Distance labeling in graphs
• Distributed computing by mobile robots: gathering
• Distributed computing with advice: information sensitivity of graph coloring
• Drawing maps with advice
• Fast radio broadcasting with advice
• Finding Your Kids When They Are Lost
• Gathering of asynchronous robots with limited visibility
• Graph searching with advice
• How to Meet in Anonymous Network
• How to meet asynchronously (almost) everywhere
• How to meet when you forget: log-space rendezvous in arbitrary graphs
• LATIN 2004: Theoretical Informatics
• Label-guided graph exploration by a finite automaton
• Labeling Schemes for Flow and Connectivity
• Local MST computation with short advice
• Minimax Rendezvous on the Line
• Online computation with advice
• Proof labeling schemes
• Randomized Rendez-Vous with Limited Memory
• Rendezvous on the Line when the Players' Initial Distance is Given by an Unknown Probability Distribution
• Rendezvous search on labeled networks
• Rendezvous search when marks are left at the starting points
• The Rendezvous Search Problem
• The rendezvous problem on discrete locations
• Trade-offs between the size of advice and broadcasting time in trees
• Tree exploration with advice
• Two Dimensional Rendezvous Search
• Volume of an N-simplex by multiple integration

Cited in

(9)

• Finding Guaranteed MUSes Fast
• Memory optimal dispersion by anonymous mobile robots
• Memory optimal dispersion by anonymous mobile robots
• Quicker than Quickhull
• Asynchronous approach in the plane: a deterministic polynomial algorithm
• Byzantine gathering in polynomial time
• Locating a target with an agent guided by unreliable local advice, how to beat the random walk when you have a clock?
• Byzantine gathering in polynomial time
• scientific article; zbMATH DE number 1696681 (Why is no real title available?)

This page was built for publication: Fast rendezvous with advice

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