Time vs. space trade-offs for rendezvous in trees - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

Time vs. space trade-offs for rendezvous in trees

Résumé

Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory of the agents. For agents with $k$ memory bits, we show that optimal rendezvous time is $\Theta(n+n^2/k)$ in $n$-node trees. More precisely, if $k \geq c\log n$, for some constant $c$, we design agents accomplishing rendezvous in arbitrary trees of unknown size $n$ in time $O(n+n^2/k)$, starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time $o(n+n^2/k)$, even in the class of lines of known length and even with simultaneous start. Finally, we prove that at least logarithmic memory is necessary for rendezvous, even for agents starting simultaneously in a $n$-node line.
Fichier principal
Vignette du fichier
tradeoffs-hal.pdf (204.86 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00646912 , version 1 (01-12-2011)
hal-00646912 , version 2 (24-10-2013)

Identifiants

  • HAL Id : hal-00646912 , version 1

Citer

Jurek Czyzowicz, Adrian Kosowski, Andrzej Pelc. Time vs. space trade-offs for rendezvous in trees. [Research Report] 2011, pp.20. ⟨hal-00646912v1⟩
283 Consultations
481 Téléchargements

Partager

Gmail Facebook X LinkedIn More