[Back]


Talks and Poster Presentations (with Proceedings-Entry):

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.



English abstract:
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.


Electronic version of the publication:
https://publik.tuwien.ac.at/files/publik_273345.pdf


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