Time versus space trade-offs for rendezvous in trees

Jurek Czyzowicz 1 Adrian Kosowski 2, 3 Andrzej Pelc 1
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
3 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Abstract : 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 size $n$ {(unknown to the agents)} 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.
Type de document :
Article dans une revue
Distributed Computing, Springer Verlag, 2014, 27 (2), pp.95-109. 〈10.1007/s00446-013-0201-4〉
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00646912
Contributeur : Adrian Kosowski <>
Soumis le : jeudi 24 octobre 2013 - 23:57:20
Dernière modification le : jeudi 15 novembre 2018 - 20:27:23
Document(s) archivé(s) le : lundi 27 janvier 2014 - 12:45:45

Fichier

tradeoffs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Jurek Czyzowicz, Adrian Kosowski, Andrzej Pelc. Time versus space trade-offs for rendezvous in trees. Distributed Computing, Springer Verlag, 2014, 27 (2), pp.95-109. 〈10.1007/s00446-013-0201-4〉. 〈hal-00646912v2〉

Partager

Métriques

Consultations de la notice

373

Téléchargements de fichiers

234