Deterministic symmetric rendezvous with tokens in a synchronous torus

Abstract

In the rendezvous problem, the goal for two mobile agents is to meet whenever this is possible. In the rendezvous with detection problem, an additional goal for the agents is to detect the impossibility of a rendezvous (e.g., due to symmetrical initial positions of the agents) and stop. We consider the rendezvous problem with and without detection for identical anonymous mobile agents (i.e., running the same deterministic algorithm) with tokens in an anonymous synchronous torus with a sense of direction, and show that there is a striking computational difference between one and more tokens. Specifically, we show that (1) two agents with a constant number of unmovable tokens, or with one movable token each, cannot rendezvous in an n x n torus if they have o(log n) memory, while they can solve the rendezvous with detection problem in an n x m torus as long as they have one unmovable token and O(log n + log m) memory; in contrast, (2) when two agents have two movable tokens each then the rendezvous problem (respectively, rendezvous with detection problem) is solvable with constant memory in an arbitrary n x m (respectively, n x n) torus; and finally, (3) two agents with three movable tokens each and constant memory can solve the rendezvous with detection problem in an n x m torus. This is the first publication in the literature that studies tradeoffs between the number of tokens, memory and knowledge the agents need in order to meet in a torus. (C) 2011 Elsevier B.V. All rights reserved.