Fabian Kuhn,

University of Freiburg


We discuss basic distributed computation and information dissemination
tasks in networks where as the basic communication primitive, nodes
can locally broadcast a bounded sized message to all their
neighbors. Such a communication assumption is natural in wireless
settings and it is particularly suited to study dynamic networks and
networks with unidirectional links. For directed networks, we show
that even if the network has diameter 2, as long as this fact is not
known to the nodes, computing even simple functions such as the
minimum of a bunch of values requires time of order essentially
sqrt{n}, where n is the number of nodes of the network. We also
review recent results on the complexity of such basic data aggregation
tasks and of simple information dissemination tasks in dynamic
networks. Finally, we discuss some novel results showing that in
ordinary static, undirected networks, the achievable throughput when
performing multiple network-wide broadcasts is tightly connected to
the vertex connectivity of the network graph.


Date: 2013-Oct-07     Time: 11:00:00     Room: 336

For more information: