[Back]

M. Zeiner, M. Schwarz, U. Schmid:
"On Linear-Time Data Dissemination in Dynamic Rooted Trees";
Discrete Applied Mathematics, 255 (2019), 307 - 319.

We study the following data dissemination problem: In a set of nodes, every node has a unique piece of information. The communication of the nodes is organized in discrete synchronous lock-step rounds. In each round every node sends all currently known pieces of information to all other nodes. Which nodes receive this message is determined by the actual communication graph, which may change from round to round.

Recently, Charron-Bost, Függer, and Nowak proved an upper bound of
rounds for the case where every communication graph is an arbitrary rooted tree. We present a new formalism, which facilitates a concise proof of this result. Moreover, we establish linear-time data dissemination bounds for certain subclasses of rooted trees. In particular, we prove that only rounds are needed if the underlying graph is a directed path. An analogous result for undirected paths is also established. Furthermore, for trees with a fixed root we relate the dissemination time to the sizes of the subtrees of the root.

Directed graphs, Rooted trees Graph sequences, Dynamic networks, Data dissemination, Broadcasting

http://dx.doi.org/10.1016/j.dam.2018.08.015

https://www.sciencedirect.com/science/article/pii/S0166218X18304542