Asynchronous Rendezvous of Anonymous Agents in Arbitrary Graphs

Two identical (anonymous) mobile agents have to meet in an arbitrary, possibly infinite, unknown connected graph. Agents are modeled as points, they start at nodes of the graph chosen by the adversary and the route of each of them only depends on the already traversed portion of the graph and, in the case of randomized rendezvous, on the result of coin tossing. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. Meeting means that both agents must be at the same time in some node or in some point inside an edge of the graph.

In the deterministic scenario we characterize the initial positions of the agents for which rendezvous is feasible and we provide an algorithm guaranteeing asynchronous rendezvous from all such positions in an arbitrary connected graph. In the randomized scenario we show an algorithm that achieves asynchronous rendezvous with probability 1, for arbitrary initial positions in an arbitrary connected graph. In both cases the graph may be finite or (countably) infinite.