Gossiping by energy-constrained mobile agents in tree networks - Publikacja - MOST Wiedzy

Wyszukiwarka

Gossiping by energy-constrained mobile agents in tree networks

Abstrakt

Every node of an edge-weighted tree network contains a data packet. At some nodes are placed mobile agents, each one possessing an amount of energy (not necessarily the same for all agents). While walking along the network, the agents spend the energy proportionally to the distance traveled and collect copies of the data packets present at the visited network nodes. An agent visiting a node deposits there copies of all currently possessed data packets and collects a copy of every data packet present at this node. Two agents meeting at a node may exchange any amount of currently possessed energy. The gossiping problem asks whether it is possible to achieve that a copy of the original data packet of each node may reach every other node of the network. We prove that the gossiping problem can be solved in time for an n-node tree network T, where k is the number of agents. Moreover, we prove that in order to compute a gossiping strategy, it is enough to start with a minimum-cost convergecast that ends with all data packets and all remaining energy being present at some node of T, and then finish with a minimum-cost broadcast from this configuration. Thus, we obtain two structural properties of the gossiping problem. First, if a gossiping is feasible and r is the first node receiving all information, then there is one that is a concatenation of a convergecast to r and a broadcast from r. Secondly, it is sufficient to consider only optimal convergecast strategies. This is natural to expect but hard to prove, as locations of agents after a convergecast (moved in this stage) are essential. Hence, the convergecast has to be optimal with regards to both spent energy as well as the resulting configuration of agents, which matters in the next stage.

Cytowania

  • 1

    CrossRef

  • 0

    Web of Science

  • 1

    Scopus

Autorzy (4)

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ły w czasopismach
Opublikowano w:
THEORETICAL COMPUTER SCIENCE nr 861, strony 45 - 65,
ISSN: 0304-3975
Język:
angielski
Rok wydania:
2021
Opis bibliograficzny:
Czyzowicz J., Dereniowski D., Ostrowski R., Rytter W.: Gossiping by energy-constrained mobile agents in tree networks// THEORETICAL COMPUTER SCIENCE -Vol. 861, (2021), s.45-65
DOI:
Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1016/j.tcs.2021.02.009
Weryfikacja:
Politechnika Gdańska

wyświetlono 150 razy

Publikacje, które mogą cię zainteresować

Meta Tagi