CZYZOWICZ, Jurek; KOSOWSKI, Adrian; PELC, Andrzej

doi:10.1007/s00446-013-0201-4

Métadonnées

Licence d’utilisation du document

CZYZOWICZ, Jurek
Département d'Informatique et d'Ingénierie [DII]

KOSOWSKI, Adrian
Networks, Graphs and Algorithms [GANG]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

PELC, Andrzej
Département d'Informatique et d'Ingénierie [DII]

Langue

Article de revue

Ce document a été publié dans

Distributed Computing. 2014-04, vol. 27, n° 2, p. 95-109

Springer Verlag

Résumé en anglais

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.< Réduire

Mots clés en anglais

rendezvous

anonymous agents

time

memory space

URI

https://oskar-bordeaux.fr/handle/20.500.12278/197696

DOI

http://dx.doi.org/10.1007/s00446-013-0201-4

Project ANR

Calculabilité et complexité en distribué - ANR-11-BS02-0014

Origine

Importé de hal

Unités de recherche

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800