Paper Info
Title
On deterministic rendezvous at a node of agents with arbitrary velocities.
Abstract
We consider the task of rendezvous in networks modeled as undirected graphs. Two mobile agents with different labels, starting at different nodes of an anonymous graph, have to meet. This task has been considered in the literature under two alternative scenarios: weak and strong. Under the weak scenario, agents may meet either at a node or inside an edge. Under the strong scenario, they have to meet at a node, and they do not even notice meetings inside an edge. Rendezvous algorithms under the strong scenario are known for synchronous agents. For asynchronous agents, rendezvous under the strong scenario is impossible even in the two-node graph, and hence only algorithms under the weak scenario were constructed. In this paper we show that rendezvous under the strong scenario is possible for agents with asynchrony restricted in the following way: agents have the same measure of time but the adversary can impose, for each agent and each edge, the speed of traversing this edge by this agent. The speeds may be different for different edges and different agents but all traversals of a given edge by a given agent have to be at the same imposed speed. We construct a deterministic rendezvous algorithm for such agents, working in time polynomial in the size of the graph, in the length of the smaller label, and in the largest edge traversal time.
Year
DOI
Venue
2018
10.1016/j.ipl.2018.01.003
Information Processing Letters
Keywords
Field
DocType
Deterministic rendezvous,Algorithms,Mobile agent,Velocity
Discrete mathematics,Graph,Asynchronous communication,Asynchrony,Tree traversal,Polynomial,Computer network,Theoretical computer science,Rendezvous,Adversary,Mathematics,Traverse
Journal
Volume
ISSN
Citations 
133
0020-0190
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Sébastien Bouchard102.70
Yoann Dieudonné222119.88
Andrzej Pelc33416246.55
Franck Petit473660.02