Abstract

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.

Citations

Authors (4)