Time versus space trade-offs for randezvous in trees - Publikacja - MOST Wiedzy

Twoje konto

zaloguj

Wyszukiwarka

Time versus space trade-offs for randezvous in trees

Abstrakt

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 memory bits, we show that optimal rendezvous time is in -node trees. More precisely, if , for some constant , we design agents accomplishing rendezvous in arbitrary trees of size (unknown to the agents) in time , starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time , 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 -node line.

Autorzy (3)

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:
Publikacja w czasopiśmie
Typ:
artykuł w czasopiśmie wyróżnionym w JCR
Opublikowano w:
DISTRIBUTED COMPUTING nr 27, wydanie 2, strony 95 - 109,
ISSN: 0178-2770
Język:
angielski
Rok wydania:
2014
Opis bibliograficzny:
Czyzowicz J., Kosowski A., Pelc A.: Time versus space trade-offs for randezvous in trees// DISTRIBUTED COMPUTING. -Vol. 27, iss. 2 (2014), s.95-109
Weryfikacja:
Politechnika Gdańska

wyświetlono 115 razy

Publikacje, które mogą cię zainteresować

How to meet when you forget: log-space rendezvous in arbitrary graphs

2011

Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs

2014

Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains

2010

Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks

2014
Meta Tagi