View article

Two mobile agents having distinct identifiers and located in nodes of an unknown anonymous connected graph, have to meet at some node of the graph. We seek fast deterministic algorithms for this rendezvous problem, under two scenarios: simultaneous startup, when both agents start executing the algorithm at the same time, and arbitrary startup, when starting times of the agents are arbitrarily decided by an adversary. The measure of performance of a rendezvous algorithm is its cost: for a given initial location of agents in a graph, this is the number of steps since the startup of the later agent until rendezvous is achieved. We first show that rendezvous can be completed at cost O(n + log l) on any n-node tree, where l is the smaller of the two identifiers, even with arbitrary startup. This complexity of the cost cannot be improved for some trees, even with simultaneous startup. Efficient rendezvous in trees …