M. Zeiner, M. Schwarz, U. Schmid:

"On linear-time data dissemination in dynamic trees";

Talk: CSASC 2018, Bratislava; 2018-09-11 - 2018-09-14; in: "CSASC 2018 - Book of Abstracts", (2018), 113.

We study the following data dissemination problem: In a set of n 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. When one piece of information

is known by all nodes, dissemination is done.

Such network models are interesting as they capture the communication behavior of wireless

communication, process crash/recovery and process mobility far better then standard static

communication models. In such distributed systems data dissemination is a pivotal task in

many applications.

Charron-Bost, Függer, and Nowak proved an upper bound of O(n log n) rounds for the case

where every communication graph is an arbitrary rooted tree. We established linear-time data

dissemination bounds for certain subclasses of rooted trees. In particular, we proved that only

(n-1) rounds are needed if the underlying graph is a directed path. Analogously, in undirected

paths Ceiling((n - 1)/2) rounds are needed. Besides these results, we will focus on similarities und

differences between the directed and undirected model and discuss open questions.

https://publik.tuwien.ac.at/files/publik_273345.pdf

Created from the Publication Database of the Vienna University of Technology.