Index Catalog // Carleton University Institutional Repository

This site uses cookies to offer you a better browsing experience. Find out more on how we use cookies and how you can change your settings.

Start Over

Filtering by: Creator Markou, Euripides Creator Krizanc, Danny

Mobile agent rendezvous in a synchronous torus

Resource Type:

Conference Proceeding

Creator:

Markou, Euripides, Kranakis, Evangelos, and Krizanc, Danny

Abstract:

We consider the rendezvous problem for identical mobile agents (i.e., running the same deterministic algorithm) with tokens in a synchronous torus with a sense of direction and show that there is a striking computational difference between one and more tokens. More specifically, we show that 1) two agents with a constant number of unmovable tokens, or with one movable token, each cannot rendezvous if they have o(log n) memory, while they can perform rendezvous with detection as long as they have one unmovable token and O(log n) memory; in contrast, 2) when two agents have two movable tokens each then rendezvous (respectively, rendezvous with detection) is possible with constant memory in an arbitrary n × m (respectively, n × n) torus; and finally, 3) two agents with three movable tokens each and constant memory can perform rendezvous with detection in a 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 such a network.

Date Created:

2006-07-10