Deterministic symmetric rendezvous with tokens in a synchronous torus ?
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 nn n  n torus if they have o(logn) o ( log n ) memory, while they can solve the rendezvous with detection problem in an nm n  m torus as long as they have one unmovable token and O(logn+logm) 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 nm n  m (respectively, nn n  n ) torus; and finally, (3) two agents with three movable tokens each and constant memory can solve the rendezvous with detection problem in an nm n  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.
rendezvous tokens synchronous torus mobile agent rendezvous with detection